← 返回题目列表

AtCoder · nupc2024_g

G. 超级累积异或

中文机器翻译题面 查看原题

配点 : 100 点

問題文

N 整数序列 A = (A_1, A_2, \dots, A_N) 。 对于

执行以下操作。 重复 K 次后 请输出 A ,否则输出

  • i=1,2, \dots ,N 替换为 A_i 该值应乘以 A_1 \oplus A_2 \oplus \dots \oplus A_i 置换为。

但是, 运算前设定中包含的 \oplus 表示按位异或。

制約

  • 1 \le N \le 2 \times 10^5
  • 1 \le K \le 10^{18}
  • 0 \le A_i < 2^{30}
  • 所有输入均为整数

部分点

附加限制 如果正确答案是满足 N \le 1000 的数据集 给出 1 点。 如果您正确回答了所有满足


入力

输入是按以下格式从标准输入给出的。

N K
A_1 A_2 \dots A_N

出力

执行以上操作 按顺序输出 K 次后 请输出 A=(A_1,A_2,\dots,A_N) 的每个元素,用空格分隔。


入力例 1

3 2
1 2 3

出力例 1

1 2 2

一开始, 在第 (A_1, A_2, A_3)=(1,2,3) 。

第一次操作后 (A_1, A_2, A_3)=(1,1 \oplus 2,1 \oplus 2 \oplus 3)=(1,3,0) 。 对于

第二次这样做时, 有 (A_1, A_2, A_3)=(1,1 \oplus 3,1 \oplus 3 \oplus 0)=(1,2,2) 。 对于


入力例 2

10 3141592653589793
528994566 21013803 220742658 357578426 605624719 350507118 731879815 393165536 215218511 161335641

出力例 2

528994566 516387885 334442543 113182357 581312282 910315380 501077747 179498003 107025756 268229637