BaoBao has just found a grid with $n$ rows and $m$ columns in his left pocket, where the cell in the $j$-th column of the $i$-th row (indicated by $(i, j)$) contains an arrow (pointing either upwards, downwards, leftwards or rightwards) and an integer $a_{i, j}$.
BaoBao decides to play a game with the grid. He will first select a cell as the initial cell and tick it. After ticking a cell (let's say BaoBao has just ticked cell $(i, j)$), BaoBao will go on ticking another cell according to the arrow and the integer in cell $(i, j)$.
- If the arrow in cell $(i, j)$ points upwards, BaoBao will go on ticking cell $(i-a_{i, j}, j)$ if it exists.
- If the arrow in cell $(i, j)$ points downwards, BaoBao will go on ticking cell $(i+a_{i, j}, j)$ if it exists.
- If the arrow in cell $(i, j)$ points leftwards, BaoBao will go on ticking cell $(i, j-a_{i, j})$ if it exists.
- If the arrow in cell $(i, j)$ points rightwards, BaoBao will go on ticking cell $(i, j+a_{i, j})$ if it exists.
If the cell BaoBao decides to tick does not exist, or if the cell is already ticked, the game ends.
BaoBao is wondering if he can select a proper initial cell, so that he can tick every cell in the grid exactly once before the game ends. Please help him find the answer.
## Input
There are multiple test cases. The first line contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains two integers $n$ and $m$ ($1 \le n \times m \le 10^5$), indicating the number of rows and columns of the grid.
For the following $n$ lines, the $i$-th line contains a string $s_i$ consisting of lowercased English letters ($|s_i| = m$, $s_{i, j} \in \{\text{`u' (ascii: 117)}, \text{`d' (ascii: 100)}, \text{`l' (ascii: 108)}, \text{`r'(ascii: 114)}\}$), where $s_{i, j}$ indicates the direction of arrow in cell $(i, j)$.
- If $s_{i, j} = \text{`u'}$, the arrow in cell $(i, j)$ points upwards.
- If $s_{i, j} = \text{`d'}$, the arrow in cell $(i, j)$ points downwards.
- If $s_{i, j} = \text{`l'}$, the arrow in cell $(i, j)$ points leftwards.
- If $s_{i, j} = \text{`r'}$, the arrow in cell $(i, j)$ points rightwards.
For the following $n$ lines, the $i$-th line contains $m$ integers $a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$ ($1 \le a_{i, j} \le \max(n, m)$), where $a_{i, j}$ indicates the integer in cell $(i, j)$.
It's guaranteed that the sum of $n \times m$ of all test cases does not exceed $10^6$.
## Output
For each test case output one line. If BaoBao can find a proper initial cell, print ``Yes`` (without quotes), otherwise print ``No`` (without quotes).
[samples]
## Note
For the first sample test case, BaoBao can select cell $(1, 2)$ as the initial cell, so that he can tick all the cells exactly once in the following order: $(1, 2), (2, 2), (2, 3), (2, 1), (1, 1), (1, 3)$.
For the second sample test case, BaoBao can only tick at most $2$ cells no matter which cell is selected as the initial cell.