Sequence Modification with XOR Operation

You are given an integer sequence \(a_1, a_2, \cdots, a_n\) consisting of \(n\) numbers and \(m\) operations.

Each operation provides two integers \(x\) and \(y\). For each operation, for every index \(i\) that satisfies the condition \[ i \oplus x = 0 \] update \(a_i\) as follows: \[ a_i \gets a_i - y \] If there is no such index \(i\) (i.e. if \(x\) is not a valid index of the sequence), then no change is made to the sequence.

Note: The condition \(i \oplus x = 0\) holds if and only if \(i = x\) when \(i\) and \(x\) are non-negative integers. In other words, each operation subtracts \(y\) from the \(x\)-th element of the sequence if it exists.

After all operations are performed, output the resulting sequence.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the size of the sequence and the number of operations respectively.

The second line contains \(n\) integers \(a_1, a_2, \cdots, a_n\) representing the initial sequence.

The following \(m\) lines each contain two integers \(x\) and \(y\), denoting an operation.

outputFormat

Output the final sequence after performing all operations. The sequence should be printed in one line with the elements separated by a single space.

sample

5 3
10 20 30 40 50
3 5
6 100
1 1

9 20 25 40 50