407508: GYM102803 L Let's Get Married

"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.

The first line contains $$$T ~ (1 \leq T \leq 10^4)$$$, denoting the number of Little K's position.

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

• $$$\texttt{1 id}$$$ for the unique number
• $$$\texttt{2 x y}$$$ for the position

It is guaranteed that all points satisfy $$$|x| + |y| \leq 10^{8}$$$

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

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

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

For $$$\texttt{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