← 返回题目列表

AtCoder · gw2015_b

B. 蚂蚁窝

中文机器翻译题面 查看原题

問題文

有一个无限宽的网格和坐标 (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