Background

ZSS has a sequence, but he is not very smart, so he comes to ask you even about an operation problem.

Problem Description

Given an integer sequence of $n$ numbers $a_1, a_2, \cdots, a_n$, there are $m$ operations. In each operation, $x, y$ are given. You need to find all $i$ such that $i \oplus x = 0$, and then do $a_i \gets a_i - y$. If there is no such $i$, then the sequence will not be changed. Here, $\oplus$ denotes the bitwise XOR operation.

After all operations are finished, you need to output this sequence.

Input Format

The first line contains two positive integers $n, m$, representing the length of the sequence and the number of operations.

The next line contains the initial sequence.

The next $m$ lines each contain two numbers $x, y$, with the meaning as described above.

Output Format

Output one line with $n$ numbers, representing the sequence after all operations.

6 1
1 1 4 5 1 1
0 7

1 1 4 5 1 1

3 1
0 3 9
1 2

-2 3 9

见文件附件的 queries3.in

见文件附件的 queries3.ans

见文件附件的 queries4.in

见文件附件的 queries4.ans

Hint

For $20\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 10^3$.

For another $20\%$ of the testdata, it is guaranteed that $x = 0$.

For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 10^6$, $-10^8 \leq y, a_i \leq 10^{8}$, and $0 \leq x \leq n$.

Translated by ChatGPT 5