Two people are playing a game. There are several piles of matches. In one move, it is allowed to take any non-zero number of matches from any pile, whoever cannot make a move loses. Determine who wins when played correctly.
Input
The first line of the input file contains a natural number N — number of heaps. The second line contains N integers — the number of matches in piles. All numbers in the input file do not exceed 100000.
Output
Print "1" if the first player wins or "2" if the second player wins. If the first player wins, in the second line print the number K — the total number of winning moves. In the following K lines print information about the winning moves — pairs of numbers listed in ascending order of the first coordinate, and if equal, in ascending order of the second coordinate. In each such pair, the first number should indicate the number of the pile, and the second — the number of matches to take from this pile.
|
Enter |
Output |
1
10 |
1
1
1 10
|
2
1 1
|
2 |