Problem Description

“Don’t wanna walk alone. So, let’s get married.”

Little Y lives in a strange town, which can be represented by a finite 2D plane. Each grid point on the 2D plane has a unique number. The unique number is generated by breadth first search. The origin point (0,0) is numbered as 0. We search for the points which is not accessed yet (in the order of top, right, bottom, left) and number them with the smallest available positive number.

$$
\begin{matrix}
& & 5 & & \\
& 7 & 1 & 6 & \\
\cdots & 4 & 0 & 2 & 8 \\
& \cdots & 3 & 9 & \\
& & \cdots & &
\end{matrix}
$$

For example, the point (1,-1) is for 9 and the point 6 is at (1,1).

One day, Little Y met Little K and quickly fell in love.

Little Y wants to follow Little K’s steps. Surprisingly, Little K will publish his location.

Once noticing the location, Little Y will go to that point. However, Little Y is not clever and need your help.

Input

The first line contains T (1 ≤ T ≤ $10^4$), denoting the number of Little K’s position.

The next T lines contains the messages in the following two ways.

$\quad \cdot$ 1 id for the unique number

$\quad \cdot$ 2 x y for the position

It is guaranteed that all points satisfy |x|+|y| ≤ $10^8$

Output

Initially, ($x_{current}, y_{current}$) is set to (0,0).

For each message, you should help Little Y in the following instructions.

For 1 id, you should output the position difference (x-$x_{current}$, y-$y_{current}$) of point id at (x,y).

For 2 x y, you should output the unique number of the point at this position.

After processing the current message, ($x_{current}, y_{current}$) will be set to (x,y).

6
1 8
2 3 3
1 14
2 5 1
1 2
1 0

2 0
66
-2 -1
70
-4 -1
-1 0