{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBaoBao 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}$.\u003c/p\u003e\n\u003cp\u003eBaoBao 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\u0027s 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)$.\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eIf the arrow in cell $(i, j)$ points upwards, BaoBao will go on ticking cell $(i-a_{i, j}, j)$ if it exists.\u003c/li\u003e\n\u003cli\u003eIf the arrow in cell $(i, j)$ points downwards, BaoBao will go on ticking cell $(i+a_{i, j}, j)$ if it exists.\u003c/li\u003e\n\u003cli\u003eIf the arrow in cell $(i, j)$ points leftwards, BaoBao will go on ticking cell $(i, j-a_{i, j})$ if it exists.\u003c/li\u003e\n\u003cli\u003eIf the arrow in cell $(i, j)$ points rightwards, BaoBao will go on ticking cell $(i, j+a_{i, j})$ if it exists.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eIf the cell BaoBao decides to tick does not exist, or if the cell is already ticked, the game ends.\u003c/p\u003e\n\u003cp\u003eBaoBao 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.\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\u003cp\u003eThe 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.\u003c/p\u003e\n\u003cp\u003eFor the following $n$ lines, the $i$-th line contains a string $s_i$ consisting of lowercased English letters ($|s_i| \u003d m$, $s_{i, j} \\in \\{\\text{\u0027u\u0027 (ascii: 117)}, \\text{\u0027d\u0027 (ascii: 100)}, \\text{\u0027l\u0027 (ascii: 108)}, \\text{\u0027r\u0027 (ascii: 114)}\\}$), where $s_{i, j}$ indicates the direction of arrow in cell $(i, j)$.\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eIf $s_{i, j} \u003d \\text{\u0027u\u0027}$, the arrow in cell $(i, j)$ points upwards.\u003c/li\u003e\n\u003cli\u003eIf $s_{i, j} \u003d \\text{\u0027d\u0027}$, the arrow in cell $(i, j)$ points downwards.\u003c/li\u003e\n\u003cli\u003eIf $s_{i, j} \u003d \\text{\u0027l\u0027}$, the arrow in cell $(i, j)$ points leftwards.\u003c/li\u003e\n\u003cli\u003eIf $s_{i, j} \u003d \\text{\u0027r\u0027}$, the arrow in cell $(i, j)$ points rightwards.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eFor 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)$.\u003c/p\u003e\n\u003cp\u003eIt\u0027s guaranteed that the sum of $n \\times m$ of all test cases does not exceed $10^6$.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line. If BaoBao can find a proper initial cell, print \"Yes\" (without quotes), otherwise print \"No\" (without quotes).\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n2 3\nrdd\nurl\n2 1 1\n1 1 2\n2 2\nrr\nrr\n1 1\n1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYes\nNo\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eFor 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).\u003c/p\u003e\n\u003cp\u003eFor the second sample test case, BaoBao can only tick at most 2 cells no matter which cell is selected as the initial cell.\u003c/p\u003e\n"}}]}