龙曲线是一条自相似的分形曲线。在这个问题中,它是由相同长度的直线段以直角连接而成的曲线。构造龙曲线的简单方法如下:取一条纸条,将其沿同一方向对折 $$$n$$$ 次,然后部分展开,使各部分以直角连接。如下所示:
在此示例中,构造了 $$$3$$$ 阶的龙曲线。一般来说,高阶龙曲线都会有低阶龙曲线作为前缀。这使得我们可以定义无限阶龙曲线,当阶数接近无穷大时,这是有限阶龙曲线的极限。
考虑四条无限阶龙曲线。每条线都从原点(点$$$(0,0)$$$)开始,每条线段的长度为$$$\sqrt2$$$。曲线的第一段分别结束于点 $$$(1,1)$$$、$$$(-1,1)$$$、$$$(-1,-1)$$$ 和 $$$(1,-1)$$$。每条曲线的第一个转弯都是左转(即第一条曲线的第二段结束于点 $$$(0,2)$$$)。在这种情况下,每个线段都是一个坐标为整数的轴对齐单位正方形的对角线,并且可以证明恰好有一个线段穿过每个这样的正方形。
给定一个点 $$$(x,y)$$$,您的任务是找到穿过对角分别为 $$$(x,y)$$$ 和 $$$(x+1,y+1)$$$ 的正方形的线段,以及该线段在该曲线上的位置。曲线编号为 $$$1$$$ 到 $$$4$$$。曲线 $$$1$$$ 穿过 $$$(1,1)$$$、$$$2$$$ 穿过 $$$(-1,1)$$$、$$$3$$$ 穿过 $$$(-1,-1)$$$ 以及 $$$4$$$ 穿过 $$$(1,-1)$$$。这些段的编号从 $$$1$$$ 开始。
输入
第一行包含一个整数 $$$n$$$ ($$$1\le n\le2\cdot10^5$$$) — 测试用例的数量。
以下 $$$n$$$ 行均包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$-10^9\le x,y\le10^9$$$) — 坐标。
输出
对于每个测试用例,打印一行包含两个整数 - 第一个是曲线的索引($$$1$$$ 和 $$$4$$$ 之间的整数,含),第二个是曲线上的位置(第一段的位置为 $$$1$$$)。
示例
输入 #1
5 0 0 -2 0 -7 -7 5 -9 9 9
输出 #1
1 1 2 2 3 189 4 186 2 68
注意
您可以使用此插图来调试您的解决方案: