B - アリ巣
Editorial
/ 
/ 
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