小明的家裡有一個大小為 $n\times n$ 的表格，每個格子上面有一個字元，而且這個字元一定是 U、D、L、R 其中一個。以下用 $(r,c)$ 來表示表格第 $r$ 行第 $c$ 列的格子，並用 $s_{r,c}$ 代表 $(r,c)$ 上面的字元。

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

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

1. 將色筆所在的格子的色塗成 $c_i$。
2. 假設現在色筆所在的格子為 $(x,y)$，則：
   • 如果 $s_{x,y}=$ U 將色筆移到 $(x-1,y)$。
   • 如果 $s_{x,y}=$ D 將色筆移到 $(x+1,y)$。
   • 如果 $s_{x,y}=$ L 將色筆移到 $(x,y-1)$。
   • 如果 $s_{x,y}=$ R 將色筆移到 $(x,y+1)$。
3. 將 $k_i$ 減一
4. 如果現在 $k_i=0$ 或是色筆超出表格邊界則終止塗色，否則回到 1.。

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