{"raw_statement":[{"iden":"statement","content":"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}$.\n\nBaoBao 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)$.\n\n- If the arrow in cell $(i, j)$ points upwards, BaoBao will go on ticking cell $(i-a_{i, j}, j)$ if it exists.\n- If the arrow in cell $(i, j)$ points downwards, BaoBao will go on ticking cell $(i+a_{i, j}, j)$ if it exists.\n- If the arrow in cell $(i, j)$ points leftwards, BaoBao will go on ticking cell $(i, j-a_{i, j})$ if it exists.\n- If the arrow in cell $(i, j)$ points rightwards, BaoBao will go on ticking cell $(i, j+a_{i, j})$ if it exists.\n\nIf the cell BaoBao decides to tick does not exist, or if the cell is already ticked, the game ends.\n\nBaoBao 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.\n"},{"iden":"input","content":"There are multiple test cases. The first line contains an integer $T$, indicating the number of test cases. For each test case:\n\nThe 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.\n\nFor 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)$.\n\n- If $s_{i, j} = \\text{`u'}$, the arrow in cell $(i, j)$ points upwards.\n- If $s_{i, j} = \\text{`d'}$, the arrow in cell $(i, j)$ points downwards.\n- If $s_{i, j} = \\text{`l'}$, the arrow in cell $(i, j)$ points leftwards.\n- If $s_{i, j} = \\text{`r'}$, the arrow in cell $(i, j)$ points rightwards.\n\nFor 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)$.\n\nIt's guaranteed that the sum of $n \\times m$ of all test cases does not exceed $10^6$."},{"iden":"output","content":"For each test case output one line. If BaoBao can find a proper initial cell, print ``Yes`` (without quotes), otherwise print ``No`` (without quotes).\n"},{"iden":"note","content":"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)$.\n\nFor the second sample test case, BaoBao can only tick at most $2$ cells no matter which cell is selected as the initial cell.\n"}],"translated_statement":null,"sample_group":[["2\n2 3\nrdd\nurl\n2 1 1\n1 1 2\n2 2\nrr\nrr\n1 1\n1 1","Yes\nNo"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}