407742: GYM102889 C 亦或骗子

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

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

现给一个长度为 n 的数组 a₁, a₂, ..., a_n。定义数组连续的一段 a_l, a_l + 1, ..., a_r 的分数为该段内所有数异或的 ，即：

需要请你给出如下信息：

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

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

第二行，共 n 个非负整数 a₁, a₂, ..., a_n (0 ≤ a_i < {2}²⁰)，表示题目描述中的数组 a_i。

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

方案的格式为：

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

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

6
6 4 2 4 1 7

1 2 3 3 3 4
1 1 1 2 2 2

9
3 9 1 10 9 6 7 1 6

1 2 3 3 4 4 5 6 6
1 1 1 1 1 2 2 2 3

3
0 0 0

1 1 1
1 2 3

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

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

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