Problem Background

ZSS has a sequence, but he is not very smart, so he has to ask you for help with an operation problem.

Problem Description

Given an integer sequence of $n$ numbers $a_1, a_2, \cdots, a_n$, there are $m$ operations. Each operation specifies $x, y$, and you need to find all $i$ such that $i \oplus x = 0$, then update $a_i$ to $a_i - y$. If there is no such $i$, the sequence remains unchanged. Here, $\oplus$ denotes the bitwise XOR operation.

After all operations, you need to output the sequence.

Input Format

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

The next line represents the initial sequence.

The following $m$ lines, each containing two numbers $x, y$, as described in the problem statement.

Output Format

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

Sample Input and Output

Sample Input #1

6 1
1 1 4 5 1 1
0 7

Sample Output #1

1 1 4 5 1 1

Sample Input #2

3 1
0 3 9
1 2

Sample Output #2

-2 3 9

Sample Input #3

See the attached file queries3.in

Sample Output #3

See the attached file queries3.ans

Sample Input #4

See the attached file queries4.in

Sample Output #4

See the attached file queries4.ans

Notes

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

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

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

见题面 Input 部分

见题面 Output 部分