25715번 - Puzzle: X-Sums Sudoku 다국어

문제

An $n\times m$ sudoku puzzle is a grid consisting of $m\times n$ regions, and each region contains $n\times m$ cells. Hence an $n\times m$ sudoku puzzle contains $nm\times nm$ cells. Every integer from 1ドル$ to $nm$ occurs exactly once in each row, each column, and each region of an $n\times m$ sudoku puzzle.

Listing the integers in a row or a column starting from some direction as a sequence of length $nm,ドル $X$ is the first integer of the sequence, and X-sum is the sum of the first $X$ integers of the sequence.

The above figure is a 4ドル\times 2$ sudoku puzzle with X-sums. The 7ドル$-th row listed from right to left is $[3,4,1,2,7,8,5,6]$ and the first integer $X$ is 3ドル,ドル so the X-sum of the 7ドル$-th row from the direction right is 8ドル=3+4+1$.

Given two positive integers $n$ and $m,ドル a direction $d,ドル and an index $x,ドル you need to find the X-sum of the $x$-th row or $x$-th column from the direction $d$ in the lexicographically smallest 2ドル^n\times 2^m$ sudoku.

Denoting $a_{i,j}$ as the $i$-th row and the $j$-th column of a sudoku puzzle $a,ドル a sudoku puzzle $a$ is lexicographically smaller than a sudoku puzzle $b$ of the same size if there exists $i$ and $j$ satisfying that $a_{i,j}<b_{i,j},ドル that $a_{x,y}=b_{x,y}$ for all $x<i,ドル and that $a_{x,y}=b_{x,y}$ for all $x=i$ and $y<j$. You can find that the above is the lexicographically smallest 4ドル\times 2$ sudoku puzzle.

입력

There are multiple test cases. The first line of input contains an integer $T$(1ドル\le T\le 10^5$), the number of test cases.

For each test case:

The only line contains two integers $n$ and $m$ (1ドル\le n,ドル $m\le 30$), a string $d,ドル and an integer $x$ (1ドル\le x\le2^{n+m}$). Here, 2ドル^n\times 2^m$ is the size of the sudoku puzzle; $d$ is the direction of X-sum, and it is one of "left", "right", "top", and "bottom"; $x$ is the index of a row or a column.

출력

For each test case:

Output an integer: the X-sum of the $x$-th row or $x$-th column from the direction $d$ in the lexicographically smallest 2ドル^n\times 2^m$ sudoku.

Note that the answer may exceed 2ドル^{64}-1$. Consider using __int128_t in C++, BigInteger in Java or Kotlin, or int in Python.

제한

힌트