AT_gw2015_b アリ巣

在一个无限大的网格上，坐标 $(0, 0)$ 处有一只蚂蚁。每个坐标位置最初都标记为 $0$，蚂蚁初始时面向上（$Y$ 轴正方向）。蚂蚁会不断重复以下动作： 1. 根据当前坐标上的数字进行转向：如果数字是 $0$，向右转 $90$ 度；如果是 $1$，向左转 $90$ 度。 2. 改变当前坐标上的数字：如果原数字是 $0$，则改为 $1$；如果是 $1$，则改为 $0$。 3. 向当前面朝的方向移动一步： - 面朝上时，位置从 $(x, y)$ 移动到 $(x, y+1)$。 - 面朝右时，位置从 $(x, y)$ 移动到 $(x+1, y)$。 - 面朝下时，位置从 $(x, y)$ 移动到 $(x, y-1)$。 - 面朝左时，位置从 $(x, y)$ 移动到 $(x-1, y)$。 请计算在第 $N$ 步前进完成后，蚂蚁所在位置的数字。

输入包含一个整数 $N$（$1 \leq N \leq 10^{18}$），表示蚂蚁完成了 $N$ 步。

请输出蚂蚁在第 $N$ 步完成后所在坐标的数字，输出结果需加换行符。 ## 示例解释 当蚂蚁行走到第 $10$ 步时，网格的状态如下所示，其中 `a` 表示蚂蚁的位置： ```plaintext 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 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 ``` **本翻译由 AI 自动生成**

### Sample Explanation 1 $ 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 ```