3422. The Jet-Black Wings

单点时限: 1.0 sec

内存限制: 512 MB


Eddy, who calls himself “The Jet-Black Wings”, is fighting against an evil organization called Dark Reunion. Then, he startled from the dream.

“I must be more powerful.” Eddy said to himself in his mind.

Eddy often practice to be a powerful fighter. During his practice, he collects $N$ magic stones. The $i$-th stone contains $A_i$ units of dark forces. Eddy does the instruction for $Q$ turns, each turn he has two choices:

  • 1 X: Use $X$ units of dark forces to all of the magic stones. Thus, the dark forces of the $i$-th magic stone changes to $A_i \oplus X$.
  • 2 K: Sort all the magic stones by their dark forces increasely and sum up the dark forces of the first $K$ magic stones.

Could you help Eddy to check whether he is correct?

Expression $x \oplus y$ means applying bitwise exclusive or operation to integers $x$ and $y$. The given operation exists in all modern programming languages, for example, in languages C++ and Java it is represented as ^, in Pascal — as xor.


The first line of each test case contains two integers $N$, $Q$, indicating the number of magic stones and the number of instructions.

The second line of each test case contains $N$ integers $A_1,A_2,\ldots,A_N$, indicating the dark forces of the $i$-th magic stone.

For the following $Q$ lines, each line contains an instruction 1 X or 2 K.

You may assume:

  • $1 \le N,Q \le 100000$
  • $0 \le A_i,X < 2 ^{31}$
  • $1 \le K \le N$


For each 2 K instruction, sum up the dark forces of the first $K$ magic stones after sorted and output in one line.

2 人解决,2 人已尝试。

2 份提交通过,共有 3 份提交。

8.0 EMB 奖励。

创建: 2 年,11 月前.

修改: 2 年,11 月前.

最后提交: 2 年,10 月前.

来源: TOPC 2017