407410: GYM102785 F Pebbles

At the computer science exam, Vasya was solving the following problem:

«Two players, Petya and Vanya, are playing the following game. In front of the players there is a pile of stones. Players take turns, Petya is the first to play. In one move, the player can add $$$a$$$ stones to the pile or increase the number of stones in the pile twice. For example, if $$$a = 2$$$, having a pile of $$$10$$$ stones, in one move you can get a pile of $$$12$$$ or $$$20$$$ stones. Each player has an unlimited amount of stones to make moves.

The game ends at the moment when the number of stones in the pile becomes at least $$$n$$$. The loser is the player who made the last move, that is, who received a pile of $$$n$$$ or more stones.

At the initial moment there were $$$s$$$ stones in the pile. It is said that a player has a winning strategy if he can win in any opponent's moves.»

Unfortunately, Vasya does not remember the values of $$$a$$$ and $$$n$$$, which were at the exam, but he remembers at which initial $$$s$$$ Petya or Vanya won. He also remembers that $$$a$$$, $$$n$$$ and $$$s$$$ did not exceed $$$10^3$$$.

Write a program which, using different values of $$$s$$$ and a winning strategy for these $$$s$$$, will find the minimum suitable $$$a$$$ and $$$n$$$.

The first line of the input file contains the number $$$k$$$ — the number of positions $$$(1 \le k \le 1000)$$$ for which Vasya remembers the outcomes.

Then follow $$$k$$$ lines, each of which contains two integers. The first of these numbers is the initial number of stones $$$s_i$$$ $$$(0 < s_i \le 1000)$$$, the second is $$$1$$$, if with the number of stones $$$s_i$$$, Petya wins, or $$$2$$$ if with this number of stones Vanya wins. All initial positions of $$$s_i$$$ are different.

The output file must contain two integers $$$n$$$ and $$$a$$$, separated by a space $$$(0 < n, a \le 1000)$$$.

If the problem allows several solutions, then a solution with a minimum $$$n$$$ must be derived; if there are several solutions for a minimum $$$n$$$, then a solution with minimal $$$n$$$ and $$$a$$$ must be derived.

If the solution does not exist, then two zeros should be output.

4
1 2
2 1
3 1
4 2

5 1

2
1 2
2 2

0 0