P8891 "UOI-R1" Query

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

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.

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 one line with $n$ numbers, representing the sequence after all operations.

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