問題文
有一个无限宽的网格和坐标 (0,0) 中有蚂蚁。对于每个整数坐标位置, 0 或 给出 1 可以写数字,首先所有坐标都是 写入 0 。起初,蚂蚁指向上方(Y 面向轴正方向),无限重复以下动作。
- 当前坐标处写入的数字为 0 如果 90 向右转,1 如果 90 向左转。
- 将当前坐标处写入的数字反转。也就是说,原来的数是 写入 0 如果 1 , 写入1 如果 0 。
-
1 向前迈出一步。也就是说,
- 蚂蚁坐标 如果您位于 (x,y) 且面朝上,则坐标 转至 (x,y+1) 。 如果您位于
- 蚂蚁坐标 如果您位于 (x,y) 且面朝右侧,则坐标 如果您位于 (x+1,y) 。 如果您位于
- 蚂蚁坐标 如果您位于 (x,y) 中且面朝下,则坐标 如果您位于 (x,y-1) 。 如果您位于
- 蚂蚁坐标 如果您位于 (x,y) 且面向左,则坐标 (x-1,y) 。 如果您位于
蚂蚁 N 向前迈出一步后,立即回答蚂蚁所在坐标处写的数字。
入力
输入是按以下格式从标准输入给出的。
N
- 1 行包含一个表示步数的整数。 N (1 ≦ N ≦ 10^{18}) 。 来自行
出力
蚂蚁 N 向前迈出一步后,立即计算蚂蚁所在坐标处所写的数字。 1 行输出。在输出末尾插入换行符。
入力例1
5
出力例1
0
10 直到步骤的网格如下。然而,a 代表蚂蚁的位置。
00000 00000 00a00 00000 00000 00000 00000 001a0 00000 00000 00000 00000 00110 000a0 00000 00000 00000 00110 00a10 00000 00000 00000 00a10 00110 00000 00000 00000 0a010 00110 00000 00000 0a000 01010 00110 00000 00000 01a00 01010 00110 00000 00000 01100 01a10 00110 00000 00000 01100 0a110 00110 00000 00000 01100 00110 0a110 00000
入力例2
9
出力例2
1
入力例3
314159
出力例3
1
入力例4
12345678987654321
出力例4
0