You are given a grid of size $$$n\times m$$$. Each cell of the grid is either empty or blocked. Tahia wants to put some robots in some of the empty cells. Each empty cell can contain any number of robots at a time. Each robot has a certain direction (left, right, up or down) associated with it.
The robots can only move to the empty cells and they cannot move outside of the grid.
At each second, if the robot can make a move in its associated direction, it changes its position. Otherwise, it changes its direction. At any time t, if the robot is in the cell of row $$$r$$$ and column $$$c$$$, denoted by ($$$r, c$$$) , at time $$$t+1$$$, it moves to one of the cells ($$$r, c-1$$$), ($$$r, c+1$$$), ($$$r-1, c$$$) or ($$$r+1, c$$$) for the directions left, right, up and down respectively. If it cannot change its position, it changes its direction from left to right, from right to left, from up to down or from down to up at that second.
You are given the configuration of the grid and the initial position and direction of all the robots (at time $$$0$$$), you have to output the position and direction of each robot at time $$$k$$$.
The first line of the input contains four integers $$$n$$$, $$$m$$$, $$$x$$$ and $$$k$$$ ($$$1\leq n, m, x, k\leq 100$$$) $$$-$$$ the number of rows, the number of columns, the number of robots and the number of seconds.
The next $$$n$$$ lines contain the configuration of the grid. Each of these $$$n$$$ lines contains $$$m$$$ characters. Each of the characters is either a '$$$\cdot$$$' or a '$$$\#$$$', where '$$$\cdot$$$' denotes an empty cell and '$$$\#$$$' denotes a blocked celll.
Each of the next $$$x$$$ lines contains two integers $$$r_i$$$, $$$c_i$$$ ($$$1\le r_i \le n, 1 \le c_i\le m$$$) followed by a character $$$d_i$$$ ($$$d_i$$$ = $$$L$$$, $$$R$$$, $$$U$$$ or $$$D$$$). Here, $$$r_i$$$ denotes the row number and $$$c_i$$$ denotes the column number of the $$$i$$$-th robot. $$$L$$$, $$$R$$$, $$$U$$$ and $$$D$$$ denotes the robot having directions left, right, up and down respectively.
You have to output the position and direction of each robot at time $$$k$$$ in the given order.
5 5 2 4 ..##. #.... ...## ###.. ....# 2 3 L 2 4 R
2 4 R 2 3 L
10 10 10 10 #......##. #.##.###.. #.#....#.. ......##.. ##.#.#..#. .##...###. #...###..# .##....... ##..#.#.## #...#.#.## 1 3 U 9 6 U 10 2 D 4 9 D 4 9 U 6 1 R 8 1 R 7 2 U 3 4 L 7 4 R
1 3 U 10 6 D 10 2 D 2 9 D 3 9 D 6 1 R 8 1 R 7 2 U 3 5 R 7 2 R
The description of the first sample is given below-
 |  |  |
 |  |
