시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 1024 MB311100.000%

문제

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.

예제 입력 1

4
2 1 top 1
2 1 bottom 2
2 1 left 3
2 1 right 4

예제 출력 1

1
34
27
3

예제 입력 2

4
11 19 top 1053766555
12 26 top 230781535210
14 10 right 8344647
7 30 right 70120568170

예제 출력 2

565741033271081135
31719572400444316026492
112693473538824
477453505821905419941