TopCoder

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

66.7% (6/9)

Tags

Description

小明的家裡有一個大小為 n×n 的表格,每個格子上面有一個字元,而且這個字元一定是 UDLR 其中一個。以下用 (r,c) 來表示表格第 r 行第 c 列的格子,並用 sr,c 代表 (r,c) 上面的字元。

一開始這個表格的每個格子都沒被塗上顏色(以 . 表示),小明接下來會依序使用 q 支色筆塗顏色,其中第 i 色筆的顏色為 ci。顏色的種類有 26 種,用小寫英文字母表示。

在小明開始使用第 i 支筆之前,他把筆放在一個起始方格 (xi,yi) 上面,並決定一個使用次數 ki。接下來他會照著以下規則使用第 i 支筆:

  1. 將色筆所在的格子的色塗成 ci
  2. 假設現在色筆所在的格子為 (x,y),則:
    • 如果 sx,y= U 將色筆移到 (x1,y)
    • 如果 sx,y= D 將色筆移到 (x+1,y)
    • 如果 sx,y= L 將色筆移到 (x,y1)
    • 如果 sx,y= R 將色筆移到 (x,y+1)
  3. ki 減一
  4. 如果現在 ki=0 或是色筆超出表格邊界則終止塗色,否則回到 1.。

在他開始塗色之前,他希望能預知表格最後的狀態,但它不擅長寫程式,請幫他預測表格的結果。

Input Format

第一行輸入兩個正整數 n,q

接下來輸入 n 行,第 i 行輸入 n 個字元 si,1,si,2,,si,n

接下來再輸入 q 行,每一行輸入三個整數和一個字元 xi,yi,ki,ci

  • 1n,q100
  • 1xi,yin
  • 1ki20
  • si,j 一定是 UDLR 其中一個。
  • ci 一定是小寫英文字母。

Output Format

輸出 n 行,第 i 行輸出 n 個字元,其中第 i 行第 j 個字元代表 (i,j) 的顏色。

Sample Input 1

3 3
URD
LUL
URR
2 2 3 a
3 1 4 b
3 2 1 c

Sample Output 1

.aa
ba.
bc.

Sample Input 2

3 3
DRD
RUL
URU
1 2 3 a
2 3 4 b
3 1 1 c

Sample Output 2

.bb
.bb
c..

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~6 ki=1 40
3 0~21 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 3
1 1000 524288 65536 1 3
2 1000 524288 65536 2 3
3 1000 524288 65536 2 3
4 1000 524288 65536 2 3
5 1000 524288 65536 2 3
6 1000 524288 65536 2 3
7 1000 524288 65536 3
8 1000 524288 65536 3
9 1000 524288 65536 3
10 1000 524288 65536 3
11 1000 524288 65536 3
12 1000 524288 65536 3
13 1000 524288 65536 3
14 1000 524288 65536 3
15 1000 524288 65536 3
16 1000 524288 65536 3
17 1000 524288 65536 3
18 1000 524288 65536 3
19 1000 524288 65536 3
20 1000 524288 65536 3
21 1000 524288 65536 3