为了准备 Fo(1)otball 杯，Little Square 学校的啦啦队员们正在尝试编排一套新动作。共有 $2^N$ 名啦啦队员，她们的身高各不相同，介于 $0$ 到 $2^N - 1$ 之间。啦啦队员们排成一排。初始时，位于位置 $i$ 的啦啦队员身高为 $h[i]$，其中 $1 \le i \le 2^N$。

啦啦队员们掌握两种协调的舞蹈动作：

• 大交换 (big swap)：在此动作中，前 $2^{N-1}$ 名啦啦队员与后 $2^{N-1}$ 名啦啦队员交换位置。
• 大拆分 (big split)：在此动作中，处于奇数位置的啦啦队员移动到队列前端，处于偶数位置的啦啦队员移动到队列末尾。

例如，对于 $8$ 个元素进行一次 big swap 的效果如下：

对于 $8$ 个元素进行一次 big split 的效果如下：

现在，定义一个身高序列为 $h[1], \dots, h[2^N]$ 的啦啦队队列的逆序对数量为满足 $1 \le i < j \le 2^N$ 且 $h[i] > h[j]$ 的数对 $(i, j)$ 的数量。啦啦队员们想知道一个舞蹈动作序列，使得最终队列中的逆序对数量最少。

输入格式

输入的第一行包含 $N$。第二行包含 $2^N$ 个整数，表示 $h[1], \dots, h[2^N]$。

输出格式

输出的第一行打印可以达到的最小逆序对数量。在输出的第二行，写出一个字符串，表示导致该最小逆序对数量的舞蹈动作序列。在该字符串中，1 代表 big swap，2 代表 big split。任何能达到最小逆序对数量的动作序列均可被接受。

数据范围

• $0 \le N \le 17$。
• $N$ 可以为 $0$。
• 如果输出的最小逆序对数量正确，但动作字符串不正确，你将获得 $X$ 分。$X$ 的值随子任务而异。
• 动作字符串的长度必须最多为 $500,000$ 个字符。

子任务

子任务 1（16 分）： $N \le 4$ $X = 8$

子任务 2（10 分）： $N \le 7$ $X = 5$

子任务 3（25 分）： $N \le 11$ $X = 20$

子任务 4（21 分）： $N \le 16$ 保证可以达到的最小逆序对数量为 $0$。 * $X = 0$

子任务 5（28 分）： 无额外限制。 $X = 21$

样例

样例输入 1

2
0 3 1 2

样例输出 1

1
2212

样例输入 2

3
2 3 7 6 1 4 5 0

样例输出 2

8
21221

样例输入 3

4
1 4 8 5 3 6 12 13 10 11 2 9 14 0 15 7

样例输出 3

43
2222