Problem D
Slicice

After their pool burst, Mirko and Slavko started collecting cards. In their neighbourhood, card collection is taken seriously and there are strict rules for the purchase and trading of cards.

Purchasing cards is always done by two children together. Each of them gives half the required funds and two cards are bought. Then they race to the fountain downtown, the winner getting both cards. If they arrive at the exact same time, each of them gets one of the cards.

At first the rules performed okay, but soon accusations started that some kids could not have acquired their cards only through such purchases.

One day all the children met to figure out if there were irregularities. They managed to agree on the exact number of cards each of them currently has. They also made a partial list of who went to the store with whom, but they do not know who won any of the races and took the cards on those occasions.

Write a program that determines the participants in all purchases that were made and who won the subsequent races so that after all the purchases, the cards counts correspond to the given counts. Assume that before any purchases, the children had no cards.

If there are multiple possible solutions, output any of them.

Input

The first line contains the integers $N$ and $M$ ($1 \le N \le 100$, $0 \le M \le 1000$), the number of children and the number of purchases they recall. The children are labeled $1$ through $N$.

The second line contains $N$ integers, the number of cards each child currently has. The total number of cards of all children is at most $2\, 000$.

The following $M$ lines contain two integers $a \ne b$ each, the labels of the children who made the purchase.

Output

On the first line, output the total number of purchases.

Each of the following lines should describe one purchase. The description of a purchase consists of three numbers: the two distinct labels of the children that made the purchase and the number $0$, $1$ or $2$, how many cards the first child got after the race.

Note: A solution will always exist, although it will not necessarily be unique.

Explanation of Sample Input 1

In the first example, there are only two children, labeled $1$ and $2$. The first child should end up with five cards, the second with one.

After the first purchase, each of the children got one card.

After the second and third purchases, the first child got both cards both times.

2 3
5 1
1 2
1 2
1 2

3
1 2 1
1 2 2
1 2 2

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

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

5 0
3 0 2 4 1

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