2018 团体程序设计天梯赛分组赛暨 3 月内部选拔

A3. 神奇的 01 字符串

单点时限: 1.0 sec

内存限制: 256 MB

有一个 01 字符串家族 $s_i$ 按如下定义:

  • $s_0 = 0$;
  • $s_i = s_{i-1} + anti(s_{i-1})$.

其中 $+$ 表示字符串的连接操作,$anti$ 表示对 01 字符串进行取反(原来 0 的变成 1,原来 1 的变成 0)。

按照这样的规则:

  • $s_0 = 0$,
  • $s_1 = 01$,
  • $s_2 = 0110$,
  • $s_3 = 01101001$,
  • $s_4 = 0110100110010110$,
  • ......

这些字符串拥有诸多神奇的性质。例如:

  1. 任意一个之前出现的字符串都是当前字符串的前缀(由定义保证)。
  2. $s_0, s_2, s_4, \ldots$ 是对称的,$s_1,s_3,s_5$ 是反对称的。
  3. 如果对某一个字符串的下标和下标上的数进行研究,你会发现是 0 还是 1 实质上与下标二进制上 1 的个数的奇偶性有关。
  4. 取二进制串对应的子集,例如 $s_4$ 对应于 $A={2,3,5,8,9,12,14,15}$,$anti(s_4)$ 对应于 $A’={1,4,6,7,10,11,13,16}$,则 $A+A=A’+A’$。其中 $A+A={x + y | x, y \in A, x \neq y}$。不相信吗?可以取 $s_2$ 验证一下。
  5. $n \ge 13$ 时可以卡掉基于自然溢出的字符串哈希。

输入格式

输入一个整数 $i$ ($0 \le i \le 15$)。

输出格式

输出 $s_i$。

样例

Input
0
Output
0
Input
1
Output
01
Input
2
Output
0110
Input
3
Output
01101001
Input
4
Output
0110100110010110