/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は、 N \times M のグリッド状に区切られた倉庫のフロアを管理しています。グリッドの各マスは、壁（#）または床（.）のいずれかです。
このフロアには K 台のロボット掃除機が配置されています。各ロボット掃除機は、毎ターン上下左右のいずれか 1 マスに移動します。ロボット掃除機は以下のルールに従って動作するようプログラムされています。
- 各ロボット掃除機には、移動の指示を表す長さ L_i の命令列 S_i が与えられている。命令列は
U（上）、D（下）、L（左）、R（右）の文字からなる。 - ターン t において、ロボット掃除機 i は命令列の ((t - 1) \bmod L_i) + 1 番目の文字が示す方向に 1 マス移動しようとする。
- 移動先がグリッドの範囲外、または壁である場合、その移動は無視され、ロボット掃除機はそのターンではその場にとどまる。
高橋君は、 T ターン後に各ロボット掃除機がどの位置にいるかを知りたいと考えています。
ロボット掃除機 i の初期位置 (R_i, C_i) （上から R_i 行目、左から C_i 列目）、命令列 S_i 、およびターン数 T が与えられるので、 T ターン後の各ロボット掃除機の位置を求めてください。
なお、複数のロボット掃除機が同じマスに存在することは許されており、ロボット掃除機同士は互いに影響を与えません。
制約
- 1 \leq N \leq 2000
- 1 \leq M \leq 2000
- N M \leq 10^6
- 1 \leq K \leq 10^5
- 1 \leq T \leq 10^{18}
- g_i は
.または#からなる長さ M の文字列である - 1 \leq R_i \leq N
- 1 \leq C_i \leq M
- ロボット掃除機 i の初期位置 (R_i, C_i) は床（
.）である - 1 \leq L_i \leq 1000
- \displaystyle\sum_{i=1}^{K} L_i \leq 2 \times 10^5
- S_i は
U,D,L,Rからなる長さ L_i の文字列である - 相異なる命令列全体の集合を \mathcal{S} とし、A = \displaystyle\sum_{S \in \mathcal{S}} |S| とする。このとき、N M (A + K) \leq 2 \times 10^7 を満たす
- 入力はすべて整数（ N, M, K, T, R_i, C_i, L_i ）および文字列（ g_i, S_i ）で与えられる
入力
N M K T g_1 g_2 : g_N R_1 C_1 L_1 S_1 R_2 C_2 L_2 S_2 : R_K C_K L_K S_K
- 1 行目には、グリッドの行数 N 、列数 M 、ロボット掃除機の台数 K 、シミュレーションするターン数 T が、スペース区切りで与えられる。
- 2 行目から N 行にわたって、グリッドの情報が与えられる。 g_i は M 文字の文字列で、
.が床、#が壁を表す。 - 続く K 行で、各ロボット掃除機の情報が与えられる。 1 + N + j 行目には、ロボット掃除機 j の初期位置の行 R_j 、列 C_j 、命令列の長さ L_j 、命令列 S_j がスペース区切りで与えられる。
出力
K 行出力せよ。 i 行目には、ロボット掃除機 i の T ターン後の位置を、行番号と列番号をスペース区切りで出力せよ。
入力例 1
3 4 2 5 .... .#.. .... 1 1 4 RRRD 3 4 3 ULL
出力例 1
2 4 1 2
入力例 2
2 3 3 4 .#. ... 1 1 1 R 1 3 2 DL 2 2 4 LRUD
出力例 2
1 1 2 1 2 2
入力例 3
8 10 6 123456789012 .......... .####..#.. .#....#... .#.#..#.#. ...#...... ##...###.. ..#....... .....#.... 1 1 4 RDDR 3 4 6 URDLDR 5 10 3 LLL 8 1 8 UURRDDLL 6 3 5 DRRUL 2 7 4 DDLU
出力例 3
8 10 6 5 5 5 7 2 6 5 7 1
入力例 4
20 30 15 987654321987654321 .............................. .####.....######......####.... .#..#.....#....#......#..#.... .#..#.....#....#......#..#.... .####.....######......####.... .............................. .....#####..........#####..... .....#..................#..... .....#..##########..#...#..... .....#..................#..... .....#####..........#####..... .............................. ..########..####..########.... ..#......#..#..#..#......#.... ..########..####..########.... .............................. ####....####....####....####.. .............................. ..#..#..#..#..#..#..#..#..#... .............................. 1 1 4 RRRD 1 30 5 LLLDD 6 15 10 DDDRRRUUUL 8 10 12 RRRRDDLLLLUU 9 7 9 DRDRULULL 12 1 16 RRRRRRDDLLLLLLUU 13 1 7 RDRDRDL 14 15 6 UDLRRL 16 30 20 LLLLUUUURRRRDDDDLLLL 18 5 3 DDD 20 30 4 ULDR 7 1 8 RRRRRRRR 11 30 10 LLLLLDDUUU 19 1 5 RDRUR 4 29 11 LLUUURRRDDD
出力例 4
10 24 20 1 9 23 8 11 9 7 10 2 20 29 14 14 14 17 20 5 19 30 7 5 1 1 19 30 4 30
入力例 5
1 1 1 1000000000000000000 . 1 1 1 U
出力例 5
1 1
Score : 433 pts
Problem Statement
Takahashi manages the floor of a warehouse divided into an N \times M grid. Each cell of the grid is either a wall (#) or a floor (.).
There are K robot vacuum cleaners placed on this floor. Each robot vacuum cleaner moves one cell up, down, left, or right every turn. The robot vacuum cleaners are programmed to operate according to the following rules:
- Each robot vacuum cleaner i is given a command sequence S_i of length L_i representing movement instructions. The command sequence consists of the characters
U(up),D(down),L(left), andR(right). - At turn t, robot vacuum cleaner i attempts to move one cell in the direction indicated by the ((t - 1) \bmod L_i) + 1-th character of its command sequence.
- If the destination is outside the grid or is a wall, the movement is ignored, and the robot vacuum cleaner stays in place for that turn.
Takahashi wants to know the position of each robot vacuum cleaner after T turns.
Given the initial position (R_i, C_i) (row R_i from the top, column C_i from the left) of robot vacuum cleaner i, its command sequence S_i, and the number of turns T, determine the position of each robot vacuum cleaner after T turns.
Note that multiple robot vacuum cleaners are allowed to occupy the same cell, and robot vacuum cleaners do not affect each other.
Constraints
- 1 \leq N \leq 2000
- 1 \leq M \leq 2000
- N M \leq 10^6
- 1 \leq K \leq 10^5
- 1 \leq T \leq 10^{18}
- g_i is a string of length M consisting of
.or# - 1 \leq R_i \leq N
- 1 \leq C_i \leq M
- The initial position (R_i, C_i) of robot vacuum cleaner i is a floor cell (
.) - 1 \leq L_i \leq 1000
- \displaystyle\sum_{i=1}^{K} L_i \leq 2 \times 10^5
- S_i is a string of length L_i consisting of
U,D,L,R - Let \mathcal{S} be the set of all distinct command sequences, and let A = \displaystyle\sum_{S \in \mathcal{S}} |S|. Then N M (A + K) \leq 2 \times 10^7 holds.
- All inputs are integers (N, M, K, T, R_i, C_i, L_i) and strings (g_i, S_i)
Input
N M K T g_1 g_2 : g_N R_1 C_1 L_1 S_1 R_2 C_2 L_2 S_2 : R_K C_K L_K S_K
- The first line contains the number of rows N, the number of columns M, the number of robot vacuum cleaners K, and the number of turns to simulate T, separated by spaces.
- The next N lines give the grid information. g_i is a string of M characters, where
.represents a floor and#represents a wall. - The following K lines give the information for each robot vacuum cleaner. The (1 + N + j)-th line contains the initial row R_j, column C_j, command sequence length L_j, and command sequence S_j of robot vacuum cleaner j, separated by spaces.
Output
Output K lines. The i-th line should contain the row number and column number of robot vacuum cleaner i after T turns, separated by a space.
Sample Input 1
3 4 2 5 .... .#.. .... 1 1 4 RRRD 3 4 3 ULL
Sample Output 1
2 4 1 2
Sample Input 2
2 3 3 4 .#. ... 1 1 1 R 1 3 2 DL 2 2 4 LRUD
Sample Output 2
1 1 2 1 2 2
Sample Input 3
8 10 6 123456789012 .......... .####..#.. .#....#... .#.#..#.#. ...#...... ##...###.. ..#....... .....#.... 1 1 4 RDDR 3 4 6 URDLDR 5 10 3 LLL 8 1 8 UURRDDLL 6 3 5 DRRUL 2 7 4 DDLU
Sample Output 3
8 10 6 5 5 5 7 2 6 5 7 1
Sample Input 4
20 30 15 987654321987654321 .............................. .####.....######......####.... .#..#.....#....#......#..#.... .#..#.....#....#......#..#.... .####.....######......####.... .............................. .....#####..........#####..... .....#..................#..... .....#..##########..#...#..... .....#..................#..... .....#####..........#####..... .............................. ..########..####..########.... ..#......#..#..#..#......#.... ..########..####..########.... .............................. ####....####....####....####.. .............................. ..#..#..#..#..#..#..#..#..#... .............................. 1 1 4 RRRD 1 30 5 LLLDD 6 15 10 DDDRRRUUUL 8 10 12 RRRRDDLLLLUU 9 7 9 DRDRULULL 12 1 16 RRRRRRDDLLLLLLUU 13 1 7 RDRDRDL 14 15 6 UDLRRL 16 30 20 LLLLUUUURRRRDDDDLLLL 18 5 3 DDD 20 30 4 ULDR 7 1 8 RRRRRRRR 11 30 10 LLLLLDDUUU 19 1 5 RDRUR 4 29 11 LLUUURRRDDD
Sample Output 4
10 24 20 1 9 23 8 11 9 7 10 2 20 29 14 14 14 17 20 5 19 30 7 5 1 1 19 30 4 30
Sample Input 5
1 1 1 1000000000000000000 . 1 1 1 U
Sample Output 5
1 1