CF1578D.Dragon Curve

A dragon curve is a self-similar fractal curve. In this problem, it is a curve that consists of straight-line segments of the same length connected at right angles. A simple way to construct a dragon curve is as follows: take a strip of paper, fold it in half $n$ times in the same direction, then partially unfold it such that the segments are joined at right angles. This is illustrated here:

In this example, a dragon curve of order $3$ is constructed. In general, a dragon curve of a higher order will have a dragon curve of a lower order as its prefix. This allows us to define a dragon curve of infinite order, which is the limit of dragon curves of a finite order as the order approaches infinity.

Consider four dragon curves of infinite order. Each starts at the origin (the point $(0,0)$), and the length of each segment is $\sqrt2$. The first segments of the curves end at the points $(1,1)$, $(-1,1)$, $(-1,-1)$ and $(1,-1)$, respectively. The first turn of each curve is left (that is, the second segment of the first curve ends at the point $(0,2)$). In this case, every segment is a diagonal of an axis-aligned unit square with integer coordinates, and it can be proven that there is exactly one segment passing through every such square.

Given a point $(x,y)$, your task is to find on which of the four curves lies the segment passing through the square with the opposite corners at $(x,y)$ and $(x+1,y+1)$, as well as the position of that segment on that curve. The curves are numbered $1$ through $4$. Curve $1$ goes through $(1,1)$, $2$ through $(-1,1)$, $3$ through $(-1,-1)$, and $4$ through $(1,-1)$. The segments are numbered starting with $1$.

龙形曲线（dragon curve）是一种自相似分形曲线。在本题中，它是由长度相等的直线段构成的曲线，且相邻线段在连接处成直角。构造龙形曲线的一种简单方法如下：取一条纸带，沿同一方向连续对折 $n$ 次，然后部分展开，使得各线段在直角处相连。如下图所示：

本例中构造的是 3 阶龙形曲线。一般地，高阶龙形曲线的前缀即为某低阶龙形曲线。因此，我们可以定义无限阶龙形曲线，即有限阶龙形曲线在阶数趋于无穷时的极限。

考虑四条无限阶龙形曲线。每条曲线均起始于原点 $(0,0)$，且每条线段长度均为 $\sqrt{2}$。这四条曲线的第一条线段终点分别为 $(1,1)$、$(-1,1)$、$(-1,-1)$ 和 $(1,-1)$。每条曲线的第一处转向均为左转（即第一条曲线的第二条线段终点为 $(0,2)$）。此时，每条线段均是某个边与坐标轴平行、顶点坐标为整数的单位正方形的对角线；可以证明：对于每一个这样的单位正方形，恰好有一条线段穿过它。

给定一点 $(x,y)$，你的任务是确定：以 $(x,y)$ 和 $(x+1,y+1)$ 为对角顶点的单位正方形所穿过的那条线段，位于四条曲线中的哪一条上；并确定该线段在对应曲线中的编号（从 1 开始计数）。四条曲线编号为 $1$ 至 $4$：曲线 $1$ 经过 $(1,1)$，曲线 $2$ 经过 $(-1,1)$，曲线 $3$ 经过 $(-1,-1)$，曲线 $4$ 经过 $(1,-1)$。

The first line contains an integer $n$ ($1\le n\le2\cdot10^5$) — the number of test cases.

Each of the following $n$ lines contains two integers $x$ and $y$ ($-10^9\le x,y\le10^9$) — the coordinates.

第一行包含一个整数 $n$（$1\le n\le2\cdot10^5$）——测试用例的数量。

接下来的 $n$ 行中，每行包含两个整数 $x$ 和 $y$（$-10^9\le x,y\le10^9$）——坐标。

For each test case, print a line containing two integers — the first is the index of the curve (an integer between $1$ and $4$, inclusive), and the second is the position on the curve (the first segment has the position $1$).

对于每个测试用例，输出一行包含两个整数——第一个是曲线的索引（一个介于 $1$ 和 $4$ 之间的整数，含端点），第二个是曲线上的位置（第一条线段的位置为 $1$）。

You can use this illustration to debug your solution:

您可以使用此图示来调试您的解法：