Chessboard Movement Simulation

This problem simulates a simplified chessboard game. You are given a grid of size N × M with some obstacles, and K chess pieces. Each chess piece has an initial position and a movement direction (up, down, left, right). The game lasts for R rounds. In each round, every chess piece will attempt to move one cell forward in its current direction. If the next cell is either outside the board or contains an obstacle, the piece does not move in that round and instead reverses its direction (rotates 180°). After R rounds, output the final positions of all chess pieces in the order of input.

Simplification note: Although the full game description involves many skills and combat rules, this problem requires you only to simulate the movement phase as described above.

Movement rules summary:

• Each piece has a direction among 'U' (up), 'D' (down), 'L' (left), and 'R' (right).
• In each round, each piece checks the next cell in its current direction. If the cell is valid (inside the board and not an obstacle), the piece moves there.
• If the move is not possible (due to an obstacle or leaving the board), the piece stays in the same cell and reverses its direction (i.e. 'U' becomes 'D', 'L' becomes 'R', etc.).

At the end of R rounds, output each piece's final row and column.

inputFormat

The first line contains four integers N, M, K and R — the number of rows, number of columns, number of chess pieces, and the number of rounds, respectively.

The second line contains a single integer P — the number of obstacles on the board.

The following P lines each contain two integers r and c (1-indexed) representing the row and column of an obstacle.

The next K lines each contain the description of a chess piece with three inputs: two integers x and y (the initial position, 1-indexed) and a character d representing its initial direction. d will be one of 'U', 'D', 'L', or 'R'.

outputFormat

Output K lines. The i-th line should contain two integers, representing the final row and column of the i-th chess piece after R rounds.

sample

5 5 2 3
2
1 3
3 3
1 1 R
5 5 U

1 1
2 5