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 who participated 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.

입력

• The first line contains the integers N and M (1 ≤ N ≤ 100, 0 ≤ M ≤ 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 following M lines contain two integers each, the labels of the children who made the purchase.

출력

Each of the following lines should describe one purchase. The description of a purchase consists of three numbers: the labels of 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 not necessarily unique. The total number of purchases will be at most 1000.

입출력 예

input 

2 3 
5 1 
1 2 
1 2 
1 2 

output 

3 
1 2 1 
1 2 2 
1 2 2 

input 

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

output 

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

input 

5 0 
3 0 2 4 1 

output 

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

sample

출처: coci 2008/2009 contest6 6/6