{"problem":{"name":"Unique XOR Path","description":{"content":"We have a grid with $N$ rows and $M$ columns. You want to write an integer between $0$ and $2^K-1$ in each square in the grid to satisfy the following condition. *   Consider a path that starts at th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc060_b"},"statements":[{"statement_type":"Markdown","content":"We have a grid with $N$ rows and $M$ columns. You want to write an integer between $0$ and $2^K-1$ in each square in the grid to satisfy the following condition.\n\n*   Consider a path that starts at the top-left square, repeatedly moves right or down to an adjacent square, and ends at the bottom-right square. Such a path is said to be **good** if and only if the total $\\mathrm{XOR}$ of the integers written on the squares visited (including the starting and ending points) is $0$.\n*   There is exactly one good path, which is the path represented by a string $S$. The path represented by the string $S$ is a path that, for each $i$ ($1 \\leq i \\leq N+M-2$), the $i$\\-th move is right if the $i$\\-th character of $S$ is `R` and down if that character is `D`.\n\nDetermine whether there is a way to write integers that satisfies the condition.\nFor each input file, solve $T$ test cases.\nWhat is bitwise $\\mathrm{XOR}$?The bitwise $\\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A \\oplus B$, is defined as follows.\n\n*   When $A \\oplus B$ is written in binary, the $k$\\-th lowest bit ($k \\geq 0$) is $1$ if exactly one of the $k$\\-th lowest bits of $A$ and $B$ is $1$, and $0$ otherwise.\n\nFor instance, $3 \\oplus 5 = 6$ (in binary: $011 \\oplus 101 = 110$).  \nGenerally, the bitwise $\\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \\dots, p_k$ is defined as $(\\dots ((p_1 \\oplus p_2) \\oplus p_3) \\oplus \\dots \\oplus p_k)$, which can be proved to be independent of the order of $p_1, p_2, p_3, \\dots, p_k$.\n\n## Constraints\n\n*   $1 \\leq T \\leq 100$\n*   $2 \\leq N,M \\leq 30$\n*   $1 \\leq K \\leq 30$\n*   $S$ is a string containing exactly $N-1$ `D`s and $M-1$ `R`s.\n*   All numbers in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach case is in the following format:\n\n$N$ $M$ $K$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc060_b","tags":[],"sample_group":[["4\n2 2 1\nRD\n4 3 1\nRDDDR\n15 20 18\nDDRRRRRRRDDDDRRDDRDRRRRDDRDRDDRRR\n20 15 7\nDRRDDDDDRDDDRRDDRRRDRRRDDDDDRRRDD","Yes\nNo\nYes\nNo\n\nAs an example, for the first case, you can make the grid as follows.\n\n11\n00"]],"created_at":"2026-03-03 11:01:14"}}