在他们的泳池破裂后，Mirko 和 Slavko 开始收集卡片。在他们的街区，卡片收集是一件非常严肃的事情，对于卡片的购买和交易有着严格的规则。

购买卡片总是由两个孩子一起进行。他们每个人支付所需资金的一半，然后购买两张卡片。接着，他们会赛跑前往市中心的喷泉，获胜者将获得这两张卡片。如果他们同时到达，则每个人各获得一张卡片。

起初，这些规则运行得很好，但很快就有人指责某些孩子不可能仅通过这种购买方式获得他们现有的卡片。

一天，所有的孩子聚集在一起，试图弄清楚是否存在违规行为。他们一致同意了每个人当前拥有的确切卡片数量。他们还整理出了一份他们记得的、谁和谁一起去过商店的部分清单，但他们不知道在这些情况下谁赢得了赛跑并拿走了卡片。

请编写一个程序，确定所有进行的购买中谁参与了，以及随后的赛跑中谁获胜，使得在所有购买之后，卡片数量与给定的数量相符。假设在任何购买之前，孩子们没有任何卡片。

如果存在多种可能的解决方案，输出其中任意一种即可。

输入格式

第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 100$，$0 \le M \le 1000$），分别表示孩子的数量和他们回忆起已进行的购买次数。孩子们的编号为 $1$ 到 $N$。

第二行包含 $N$ 个整数，表示每个孩子当前拥有的卡片数量。

接下来的 $M$ 行，每行包含两个整数，表示进行该次购买的两个孩子的编号。

输出格式

第一行输出购买的总次数。

接下来的每行描述一次购买。一次购买的描述由三个整数组成：参与购买的两个孩子的编号，以及一个数字（$0$、$1$ 或 $2$），表示在赛跑后第一个孩子获得了多少张卡片。

注意：保证一定存在解，但不一定唯一。总购买次数最多为 $1000$。

样例

输入样例 1

2 3
5 1
1 2
1 2
1 2

输出样例 1

3
1 2 1
1 2 2
1 2 2

输入样例 2

4 3
5 3 1 1
1 3
2 3
4 1

输出样例 2

5
1 3 1
2 3 2
4 1 0
2 4 1
1 3 2

输入样例 3

5 0
3 0 2 4 1

输出样例 3

5
1 2 2
1 3 1
4 2 2
3 4 0
3 5 1

说明

在第一个样例中，只有两个孩子，编号为 $1$ 和 $2$。第一个孩子最终应该得到 $5$ 张卡片，第二个孩子得到 $1$ 张。

在第一次购买后，每个孩子各得到 $1$ 张卡片。

在第二次和第三次购买后，第一个孩子两次都获得了全部 $2$ 张卡片。