传统题 10000ms 1024MiB

Prefix XORs

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Prefix XORs

Time Limit: 10s

Memory Limit: 1024 MB

Problem Statement

You are given an integer sequence of length NN: A=(A1,A2,,An)A=(A_1,A_2,\dots,A_n), and an integer MM.

For each k=1,2,,Mk=1,2,\dots,M, find the value of A={A1,A2,,An}A=\{A_1,A_2,\dots,A_n\} after doing the operation below kk times.

  • For every i(1iN)i(1\leq i\leq N), replace the value AiA_i with A1A2AiA_1\bigoplus A_2\bigoplus\dots\bigoplus A_i.
  • Note that once the previous number AiA_i is modified, the subsequent numbers should also be operated with this new AiA_i.

Here, \bigoplus denotes bitwise XOR.

  • What is bitwise XOR?
    • The bitwise XOR of non-negative integers AA and BB, ABA\bigoplus B, is defined as follows.
    • When ABA\bigoplus B is written in base two, the digit in the 2k2^k's place (k0k\geq0) is 11 if exactly one of AA and BB is 11, and 00 otherwise.

Input

The first line contains two integers N,M(1N105,1M109)N,M(1\leq N\leq10^5,1\leq M\leq10^9).

The second line contains NN integers A1,A2,,AN(0Ai<230)A_1,A_2,\dots,A_N(0\leq A_i<2^{30}).

Output

Print the answer NN integers after MM operations, separated by spaces.

3 2
2 1 3
2 1 1
10 12
721939838 337089195 171851101 1069204754 348295925 77134863 839878205 89360649 838712948 918594427
721939838 337089195 171851101 1069204754 1069907851 277835428 942783328 988367899 624897153 844652404

Explanation

For the first sample, each operation changes AA as follows.

  • Initially : A=(2,1,3)A=(2,1,3).
  • After the first operation : A=(2,3,0)A=(2,3,0)
  • After the second operation: A=(2,1,1)A=(2,1,1)

福建师范大学第十九届程序设计竞赛重现赛

未参加
状态
已结束
规则
IOI
题目
13
开始于
2022-5-21 6:30
结束于
2023-4-19 14:30
持续时间
8000 小时
主持人
参赛人数
32