Mandarin chinese
, Russian and Vietnamese as well.
You are given a grid with $n$ rows and $m$ columns. Each cell of this grid can either be empty or it contains one particle. It can never contain more than one particle. Let's denote the cell in the $i$-th row and $j$-th column by $(i, j)$, with the top left corner being $(0, 0)$. From a cell $(i, j)$, a particle could move in one of the following four directions:
- to the left, i.e. to the cell $(i, j - 1)$
- to the right, i.e. to the cell $(i, j + 1)$
- up, i.e. to the cell $(i - 1, j)$
- down, i.e. to the cell $(i + 1, j)$
It is not possible for a particle to move to a cell that already contains a particle or to a cell that does not exist (leave the grid).
It is possible to apply a force in each of these directions. When a force is applied in a given direction, all particles will simultaneously start moving in this direction as long as it is still possible for them to move.
You are given a sequence of forces. Each subsequent force is applied only after all particles have stopped moving. Determine which cells of the grid contain particles after all forces from this sequence are applied in the given order.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $n$ and $m$.
- $n$ lines describing the initial grid follow. For each $i$ ($1 \le i \le n$), the $i$-th of these lines contains a binary string with length $m$ describing the $i$-th row of the grid. For each $j$ ($1 \le j \le m$), if the $j$-th character of this string is '1', then the cell $(i, j)$ contains a particle, and if it is '0', then the cell $(i, j)$ is empty.
- The last line contains a single string $S$ describing the sequence of applied forces. Each character of this string corresponds to applying a force in some direction; forces applied in the directions left, right, up, down correspond to characters 'L', 'R', 'U', 'D' respectively.

-----Output-----
For each test case, print $n$ lines each containing a binary string of length $m$, describing the resulting grid (after all the forces are applied) in the same format as the input grid.

-----Constraints-----
- $1 \le T \le 200$
- $1 \le n, m \le 100$
- $1 \le |S| \le 2 \cdot 10^4$

-----Subtasks-----
Subtaks #1 (30 points):
- $1 \le T \le 10$
- $1 \le n, m \le 10$
- $1 \le |S| \le 100$
Subtask #2 (70 points): Original constraints

-----Example Input-----
3
4 4
1010
0010
1001
0100
LRDU
4 3
000
010
001
101
LRL
3 2
01
10
00
D

-----Example Output-----
0011
0011
0001
0001
000
100
100
110
00
00
11

-----Explanation-----
Example case 1: The initial grid is:
1010
0010
1001
0100

After applying the first force (in the direction "L", i.e. to the left), the grid is:
1100
1000
1100
1000

After applying the second force (in the direction "R"), the grid is:
0011
0001
0011
0001

After applying the third force (in the direction "D"), the grid is:
0001
0001
0011
0011

After applying the fourth force (in the direction "U"), the final grid is:
0011
0011
0001
0001

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def main():\n for _ in range(int(input())):\n  rows,column = map(int,input().split())\n  arr = []\n  for i in range(rows):\n   arr.append(list(input()))\n  string = input()\n  last = string[-1]\n  operation = Find(string,last)\n  for i in string[0]+operation:\n   if i == "L":\n    arr = Left(arr)\n   if i == "R":\n    arr = Right(arr)\n   if i == "U":\n    arr = Transpose(arr)\n    arr = Left(arr)\n    arr = Transpose(arr)\n   if i == "D":\n    arr = Transpose(arr)\n    arr = Right(arr)\n    arr = Transpose(arr)\n  for i in arr:\n   print(i)\ndef Left(arr):\n for i in range(len(arr)):\n  ans = arr[i].count("1")\n  arr[i] = "1"*ans + (len(arr[i]) - ans)*"0"\n return arr\ndef Right(arr):\n for i in range(len(arr)):\n  ans = arr[i].count("1")\n  arr[i] = (len(arr[i]) - ans)*"0"+"1"*ans\n return arr\ndef Transpose(arr):\n ansss = []\n ans = list(map(list, zip(*arr)))\n for i in ans:\n  ass = i\n  hello = ""\n  for j in ass:\n   hello += j\n  ansss.append(hello)\n return ansss \ndef Find(string,last):\n for i in string[-2::-1]: \n  if last == "L":\n   if i in ["D","U"]:\n    last = i + last\n    break\n  if last == "R":\n   if i in ["D","U"]:\n    last = i + last\n    break\n  if last == "D":\n   if i in ["L","R"]:\n    last = i + last\n    break\n  if last == "U":\n   if i in ["L","R"]:\n    last = i + last\n    break\n return last\n \ndef __starting_point():\n main()\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 14877