Problem C
Playing with Numbers

You have a list of $N$ numbers, each of the form $2^a{3}^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\le N\le 50000$). The following $N$ lines each contains a pair of integers $a_i$ and $b_i$ ($0\le a_i,b_i\le 1000$), 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^{\prime }$ and $b^{\prime }$. The first pair of integers $a$ and $b$ indicate that the largest possible outcome is $2^a{3}^b$ with $i-1$ “$gcd$” operations (and therefore $N-i$ “$\mathrm{lcm}$” operations). The second pair of integers $a^{\prime }$ and $b^{\prime }$ indicate that the smallest possible outcome is $2^{a^{\prime }}{3}^{b^{\prime }}$, again with $i-1$ “$gcd$” operations.

Explanation for sample data

The three numbers are $2^0{3}^0=1$, $2^1{3}^2=18$, and $2^2{3}^0=4$.

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

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

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

3
0 0
1 2
2 0

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