The Jet-Black Wings

英文題目敘述

"AHHHHHHHHH..."

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".

英文輸入說明

On the first line there is a single integer $T$ indicating the number of test cases.

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:

$T \le 1000$
$1 \le N, Q \le 100000$
$0 \le A_i, X < 2^{31}$
$1 \le K \le N$
There are at most $5$ test cases with $N + Q > 200$.

英文輸出說明

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

範例輸入

範例輸出

17
7
3

中文題目敘述

「呃啊...可惡！...要發狂了嗎！」

艾迪，一個自稱為「漆黑之翼」的人，正在與名為「Dark Reunion」的邪惡組織作戰。接著他就驚醒了，原來只是一場夢阿...

「我一定要變得更強。」艾迪在心中激勵自己。

為了成為一名強悍的戰鬥者，艾迪認真的鍛鍊自己。在他的練習中，他收集了 $N$ 顆魔法石頭，第 $i$ 顆魔法石頭有著 $A_i$ 單位的黑暗力量。艾迪會進行 $Q$ 次操作，每次操作有以下兩種：

$1\ X$: 使用 $X$ 單位的黑暗力量於每顆魔法石頭. 因此，第 $i$ 顆魔法石頭的暗黑力量會變成 $A_i \oplus X$ 單位。
$2\ K$: 將所有的魔法石頭按照他們的黑暗力量由小到大排序，並加總前 $K$ 顆魔法石頭的黑暗力量。

你能夠幫助艾迪確認他是否正確嗎？

$x \oplus y$ 表示將 $x$ 與 $y$ 進行互斥或操作。這個操作存在於所有常用的程式語言中，例如：C++ 與 Java 即是使用「^」，而 Pascal 則使用「xor」。

中文輸入說明

第一行有一個數字 $T$，表示有 $T$ 組測試資料。

每組測試資料的第一行有兩個數字 $N$, $Q$，表示艾迪蒐集的魔法石頭個數與訓練的操作次數。

每組測試資料的第二行有 $N$ 個數字 $A_1, A_2, \ldots, A_N$，其中 $A_i$ 表示第 $i$ 顆魔法石頭的黑暗力量。

接著有 $Q$ 行，每行為一個操作「$1\ X$」或「$2\ K$」。

可假設：

$T \le 1000$
$1 \le N, Q \le 100000$
$0 \le A_i, X < 2^{31}$
$1 \le K \le N$
至多只有 $5$ 組測試資料的 $N + Q > 200$。

中文輸出說明

對於每個操作「$2\ K$」輸出一個數字於一行，表示排序後前 $K$ 顆魔法石頭的黑暗力量總和。

Judge Setting

run-time limit: 3000 ms
memory limit: 65536000 byte
測資數量: 0