Vasya was treated to sweets, and he decided to share some of the sweets with his younger brother Petya. However, he wants to share the sweets not equally, but brotherly.
To do this, Vasya decided to play the next game with himself. He spread the sweets on the table into several piles, which he arranged in a row. If there are at least two heaps, then from the first and last heaps in this row, he chooses the one in which there are fewer sweets. Let there be B sweets in the smallest pile. Then he shifts B sweets from the first pile to the second, and also shifts B sweets from the last pile to the penultimate one. At the same time, of course, one of the piles (or even two, if the first and last piles of sweets were equally divided) becomes empty, and Vasya forgets about its existence. He repeats these operations until one or two piles remain on the table.
If there is one pile left, then Vasya will eat all the candies himself, and if two — then he will eat candies from the first pile himself, and give Petya from the second pile.
Write a program that, based on the initial distribution of sweets in piles, will determine how Vasya's game will end.
Input
The initial arrangement of piles of sweets will be described by K pairs of numbers A
i, N
i, which indicate that N
i piles of sweets are laid out in a row on the table, A
i chocolates in each.
In the input file, the number K is given first (1≤K≤10
5). Then comes K pairs of numbers Ai, Ni (1≤A
i≤100, 1≤N
i≤10
8). The total number of heaps will also not exceed 10
8.
Imprint
In the output file print first 1 or 2 — the number of candy piles that will remain at the end of the game. Then output one or two numbers — the number of sweets in the remaining piles.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
3
2 2
3 2
2 1
| 2
11 1
| Initially, the candies are placed in the following piles: 2 piles of 2 candies, two piles of 3 candies, and one of 2:
2 2 3 3 2
Further, 2 candies are transferred from 1 and 5 piles to 2 and 4, while the 1 and 5 piles become empty, i.e. only 3 piles remain on the table:
4 3 5
Now 4 candies are transferred from piles 1 and 3 to pile 2 and two piles remain on the table, the game ends with the result 11 1
|
| 2 |
1
17 |
1
7 |
Initially, we have 7 piles of 1 candy in each. After the first shift, the following configuration will be obtained:
2 1 1 1 1 2
After the second:
3 1 3
After the third one, there will be one pile with 7 candies. |
| 3 |
5
1 1
2 1
3 1
4 1
5 2 |
2
15 5 |
Initially there are 6 piles:
1 2 3 4 5 5
After the first shift we get:
3 3 4 6 4
After the second:
6 4 9 1
After the third:
5 5 10
Finally, we get:
15 5 |