Hamsters on the cake
After rescuing two of their friends from the ventilation system, the hamsters decided to throw a fun celebration. They invited all the Smeshariki, started sipping tea, and nibbling on everything they could find. Then, the hamsters brought out a huge bagel and proposed a game to the Smeshariki. The Smeshariki take turns giving commands to the hamsters, who then run around the bagel to carry them out.
The bagel is represented as a checkered torus with dimensions W*H. A total of N hamsters are participating in the celebration. Each hamster is unique, so for simplicity, we will number them from 0 to N-1. After their rescue, the hamsters have become much smarter and can now follow a set of complex commands. The next command is given to the hamster whose number is equal to the sum of the coordinates of all hamsters, modulo N. The commands are as follows:
- Left L: If there are other hamsters on the same horizontal line, move one cell to the left of the nearest hamster to the left. If there are none, move one cell to the left. - Similarly, commands R, U, D are used for moving right, up, and down, respectively.
Determine the final positions of all the hamsters after the game.
Input
The first line contains three integers: W, H—the horizontal and vertical dimensions of the torus (H, W ≤ 100000), and N—the number of hamsters (N ≤ 1000). The second line contains N pairs of numbers representing the initial coordinates of the hamsters. The hamsters are numbered starting from zero. The coordinates are within the size of the bagel: 0 ≤ X < W, 0 ≤ Y < H. The penultimate line contains M—the number of commands, where 0 ≤ M ≤ 1000. The last line lists the commands, separated by spaces.
Output
For each i-th hamster, output its coordinates after executing the commands on the i-th line.