SP1876 DRAGONCU - Dragon Curves

定义$r(s)$为二进制字符串$s$翻转之后的补码，即先把二进制串$s$翻转，然后把所有的$0$变为$1$，把所有的$1$变成$0$。 然后，我们如下定义一个二进制串的数列：$s_0=1$，$s_n=s_{n-1}1r(s_{n-1})$，即： $s_0=1$ $s1=110$ $s2=1101100$ $s3=110110011100100$ 这之后，我们为一个机器人编程，使它每秒移动$1$个单位，并且根据$s_{10}$的二进制码来确定是接下来左转弯还是右转弯，转弯均为直角弯。在第$k$轮，若$s_{10}$的第$k$位数码是$1$，则机器人将向左转弯，若为$0$则将向右转弯。原文里的图表明了机器人的整个移动轨迹。 一开始的时候，机器人处于原点$(0,0)$处，并且面朝东方（即图中的白色圆圈）。在$2048$秒之后，它会处在点$(-32,32)$（即图中的黑色点）。机器人的运动轨迹被称为**龙曲线**(dragon curve)，这是一种非常著名的分形模型。 现在，机器人的程序被输入了$s_{30}$，其它的所有条件均不变，它将会一直运行直到$2^{31}$秒后停下。给出一个时间，我们现在想要知道机器人运行到的坐标。

输入包含多组数据。每一组数据占一行，包含一个数$n(n\leq10^9)$。输入数据以一个数$-1$结束。保证输入不超过$5000$组。

输出有多组。对于每一个给定的$n$，输出在$s_{30}$的调控之下，机器人开始执行程序$n$秒后，它所在的位置。输出数据应占一行，以坐标形式$(x,y)$给出。 # 样例输入 1 2 3 2048 1000000000 -1 # 样例输出 (1,0) (1,1) (0,1) (-32,32) (9648,-31504)