C. [百度之星 2025] GCD Xor MEX

定义一个可重集合 的 mex 为不在 中的最小非负整数。

小度熊有 个非负整数 。你需要从中选择 个数组成一个可重集合 ，求 的 和 的异或和的最大值。同时，他希望你对于 均求出答案。

其中可重集合 的 表示 中所有非 数的最大公约数，例如 ，。特殊地，定义任意多个 的 为 。

第一行一个整数 （）。

第二行 个整数 （）。

输出一行 个整数，第 个整数表示 时的答案。

样例 1

输入：

5
0 1 3 5 6

输出：

6 7 3 3 3

样例 2

输入：

8
0 0 1 1 5 10 15 18

输出：

18 19 19 4 4 3 3 3

对于第一组样例：

• 时，其中一种选数方案为选择 和 ，此时 ，，异或和为 ；
• 时，其中一种选数方案为选择 ，此时 ，，异或和为 。