Hamsters on the Torus#214
After rescuing two of their friends from the ventilation system, the hamsters decided to throw a celebration. They invited their friends, drank tea, and ate everything they could find. Then, the hamsters brought out a huge bagel and proposed a game. The friends take turns giving commands to the hamsters, who run around the bagel following those commands.
The bagel is represented as a checkered torus with dimensions W \times H. A total of hamsters participate in the celebration. All hamsters are unique, so for simplicity, we will number them from to N-1. After their rescue, the hamsters have become much smarter and can now perform complex sequences of commands. The next command is given to the hamster whose number is equal to the sum of the coordinates of all hamsters, modulo . The commands are as follows:
Left : If there are other hamsters on the same horizontal line, move to the cell immediately left of the closest hamster to the left. If there are none, move one cell to the left.
Similarly, the commands , , and are used for moving right, up, and down, respectively.
Determine the final positions of all the hamsters after the game.
The first line contains three integers: , (1 \leq W, H \leq 100\,000) — the horizontal and vertical dimensions of the torus, and (1 \leq N \leq 1\,000) — the number of hamsters. The second line contains pairs of integers representing the initial coordinates of the hamsters. Hamsters are numbered starting from zero. Coordinates must satisfy 0 \leq X < W, 0 \leq Y < H. The penultimate line contains (0 \leq M \leq 1\,000) — the number of commands. The last line lists the commands, separated by spaces.
For each -th hamster, output its coordinates after executing all commands on the -th line.
Example 1