Bunnyland Dwarf Thumping

Bunnyland has a giant grid field with dimensions \(10^9 \times 10^9\). There are \(n\) rabbits, each starting at a unique cell \((r, c)\). A sequence of \(m\) thumps occurs; at the beginning of the \(j\)-th second, the \(t[j]\)-th rabbit thumps. When a rabbit \(A\) thumps, every other rabbit \(B\) moves away from \(A\) as follows:

• If \(|r_A - r_B| < |c_A - c_B|\), then \(B\) moves two columns away from \(A\) (i.e. its column changes by \(2\) in the direction away from \(A\)).
• If \(|r_A - r_B| = |c_A - c_B|\), then \(B\) moves one row and one column away from \(A\) (diagonally, i.e. each coordinate changes by \(1\) in the proper direction).
• If \(|r_A - r_B| > |c_A - c_B|\), then \(B\) moves two rows away from \(A\) (i.e. its row changes by \(2\) in the direction away from \(A\)).

After all thumps, output the final positions of the \(n\) rabbits. It is guaranteed that no rabbit will leave the grid and that all rabbits will remain in distinct cells.

inputFormat

The first line contains two integers \(n\) and \(m\) — the number of rabbits and the number of thumps.

The next \(n\) lines each contain two integers \(r[i]\) and \(c[i]\), representing the initial row and column of the \(i\)-th rabbit.

The following \(m\) lines each contain a single integer \(t[j]\), indicating that the \(t[j]\)-th rabbit thumps at the beginning of the \(j\)-th second.

outputFormat

Output \(n\) lines. The \(i\)-th line should contain two integers representing the final row and column of the \(i\)-th rabbit.

sample

3 1
5 5
5 7
7 5
2

5 3
5 7
8 4