C. 亦或骗子
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

对于非负整数 u, v 的异或 ，w 二进制下第 i 位为 1，当且仅当 u 和 v 二进制下的第 i 位不相同。

非负整数 x 的 ，定义为 x 二进制下 1 的个数，比如 , , 。

现给一个长度为 n 的数组 a1, a2, ..., an。定义数组连续的一段 al, al + 1, ..., ar 的分数为该段内所有数异或的 ，即：

需要请你给出如下信息：

  1. 请给出数组 ai 的一个分段方案，使得各段分数的总和最大；
  2. 请给出数组 ai 的一个分段方案，使得各段分数的总和最小。
Input

第一行，一个正整数 n (1 ≤ n ≤ {10}5)，表示数组的长度。

第二行，共 n 个非负整数 a1, a2, ..., an (0 ≤ ai < {2}20)，表示题目描述中的数组 ai。

Output

按顺序输出两个数组分段的方案，第一个方案需使得分数和最大，第二个方案需使得分数和最小。

方案的格式为：

  • 一行，n 个正整数 si (1 ≤ si ≤ n, 1 ≤ i ≤ n)，表示原数组中第 i 个整数分在了第 si 段。需要满足 s1 = 1，以及

注意：方案不需要段数最小或最大，只要各段分数总和最大化或最小化即可。如果有多种方案，则给出任意一种即可。

Examples
Input
6
6 4 2 4 1 7
Output
1 2 3 3 3 4
1 1 1 2 2 2
Input
9
3 9 1 10 9 6 7 1 6
Output
1 2 3 3 4 4 5 6 6
1 1 1 1 1 2 2 2 3
Input
3
0 0 0
Output
1 1 1
1 2 3
Note

第一个样例中，最大的各段分数总和为 9，最小的各段分数总和为 1。

第二个样例中，最大的各段分数总和为 17，最小的各段分数总和为 3。

第三个样例中，最大的各段分数总和为 0，最小的各段分数总和也为 0。