B - アリ巣

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

無限に広いグリッドのがあり、座標 (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