X-합 스도쿠

$n\times m$ 스도쿠는 $m\times n$개의 영역으로 이루어진 격자이며, 각 영역에는 $n\times m$개의 칸이 있다. 따라서 $n\times m$ 스도쿠에는 $nm\times nm$개의 칸이 있다. 1부터 $nm$까지의 정수는 각 행, 각 열, 각 영역에 정확히 한 번씩 나타난다.

행이나 열의 정수를 어느 한 방향에서 시작해 길이 $nm$인 수열로 나열한다. 수열의 첫 번째 정수를 $X$라고 하면, X-합은 수열의 처음 $X$개 정수의 합이다.

위 그림은 X-합이 표시된 $4\times 2$ 스도쿠이다. 오른쪽에서 왼쪽으로 나열한 7번째 행은 $[3,4,1,2,7,8,5,6]$이다. 첫 정수 $X$는 3이므로, 오른쪽 방향에서 본 7번째 행의 X-합은 $8=3+4+1$이다.

두 양의 정수 $n$, $m$, 방향 $d$, 인덱스 $x$가 주어진다. 사전순으로 가장 작은 $2^n\times 2^m$ 스도쿠에서, 방향 $d$에서 본 $x$번째 행 또는 $x$번째 열의 X-합을 구하라.

크기가 같은 두 스도쿠 $a$, $b$에 대해, $a_{i,j}<b_{i,j}$인 $i$, $j$가 존재하고, 모든 $x<i$에 대해 $a_{x,y}=b_{x,y}$이며, $x=i$이고 $y<j$인 모든 칸에서 $a_{x,y}=b_{x,y}$이면, $a$는 $b$보다 사전순으로 작다.

첫 줄에 테스트 케이스의 수 $T$ ($1\le T\le 10^5$)가 주어진다.

각 테스트 케이스는 한 줄이며, 정수 $n$, $m$ ($1\le n, m\le 30$), 문자열 $d$, 정수 $x$ ($1\le x\le 2^{n+m}$)가 주어진다. 스도쿠의 크기는 $2^n\times 2^m$이다. 방향 $d$는 left, right, top, bottom 중 하나이다. $x$는 행 또는 열의 번호이다.

각 테스트 케이스마다 사전순으로 가장 작은 $2^n\times 2^m$ 스도쿠에서, 방향 $d$에서 본 $x$번째 행 또는 $x$번째 열의 X-합을 한 줄에 정수 하나로 출력한다.

답은 $2^{64}-1$을 넘을 수 있다.