Problem C
Playing with Numbers

You have a list of $N$ numbers, each of the form $2^ a3^ b$ for some non-negative integers $a$ and $b$. You want to perform $N-1$ operations on these numbers. Each operation acts on two numbers $X$ and $Y$ of your choice from the list, replacing them with a new number $\mathrm{op}(X, Y)$. After each operation, your list has one fewer number.

In this task, an operation $\mathrm{op}$ can be $\gcd $ or $\mathrm{lcm}$ (they stand for greatest common divisor and least common multiple, respectively). There are a total of $N$ scenarios: You may apply “$\gcd $” operations $k$ times and “$\mathrm{lcm}$” operations $N - 1 - k$ times. For each of the $N$ scenarios, what is the largest possible outcome after these $N-1$ operations? What about the smallest possible outcome?

Input

The first line consists of a single integer $N$ ($1 \leq N \leq 50\, 000$). The following $N$ lines each contains a pair of integers $a_ i$ and $b_ i$ ($0 \leq a_ i, b_ i \leq 1\, 000$), indicating that the $i$th number in your initial list is $2^{a_ i}3^{b_ i}$.

Output

Output $N$ lines in total. On line $i$ ($i = 1, \dots , N$), output four space-separated integers $a, b, a’$ and $b’$. The first pair of integers $a$ and $b$ indicate that the largest possible outcome is $2^ a3^ b$ with $i-1$ “$\gcd $” operations (and therefore $N-i$ “$\mathrm{lcm}$” operations). The second pair of integers $a’$ and $b’$ indicate that the smallest possible outcome is $2^{a'}3^{b'}$, again with $i-1$ “$\gcd $” operations.

Explanation for sample data

The three numbers are $2^03^0 = 1$, $2^13^2 = 18$, and $2^23^0 = 4$.

1. When $i = 0$, we can only take $\mathrm{lcm}$. $\mathrm{lcm}(1, 18, 4) = 36 = 2^23^2$.

2. When $i = 1$, the largest outcome is $\mathrm{lcm}(18, \gcd (1, 4)) = 18 = 2^13^2$, and the smallest outcome is $\gcd (1, \mathrm{lcm}(18, 4)) = 1 = 2^03^0$.

3. When $i = 2$, we can only take $\gcd $. $\gcd (1, 18, 4) = 1 = 2^03^0$.

3
0 0
1 2
2 0

2 2 2 2
1 2 0 0
0 0 0 0