8567: X-Sums Sudoku

一$m$数独拼图是一个网格，由m×n区域，并且每个区域包含$n\times m$细胞。因此，一个$m$数独拼图包含nm×nm细胞。每个整数来自1自nm在每行、每列和每个区域中恰好出现一次$\times m$数独拼图。

将行或列中的整数从某个方向开始作为长度序列列出nm,$X$是序列的第一个整数，X-sum 是第一个整数之和$X$序列的整数。



上图是一个$4\times 2$数独拼图与X-和。这$7$-从右到左列出的第一行是$[3，4，1，2，7，8，5，6]$和第一个整数$X$是$3$，因此 X-和$7$-第一行从右边的方向是$8=3+4+1$.

给定两个正整数n和$m$，方向d和索引$x$，您需要找到 X-和$x$-第一行或$x$-第 1 列从方向$d$在词典中最小的 2n×2m数独。

表示ai,ja_{i，j}一个i，j作为$我$-第 1 行和$j$-数独谜题的第 1 列a一个，数独谜题a一个在字典上比数独谜题小$b$如果存在，则大小相同$我$和$j$满足于ai,j<bi,ja_{i，j}<b_{i，j}一个i，j<bi，j那ax,y=bx,ya_{x，y}=b_{x，y}一个x，y=bx，y面向所有人$x<我$，并且ax,y=bx,ya_{x，y}=b_{x，y}一个x，y=bx，y面向所有人$x=我$和y<jy<jy<j.您可以发现以上是词典上最小的$4\times 2$数独拼图。

输入描述:

有多个测试用例。第一行输入包含一个整数TT(1\le T\le 10^51≤T≤10)5)，测试用例的数量。对于每个测试用例:唯一一行包含两个整数nn和mm (1\le n1≤n, m\le 30m≤30)，一个字符串dd和一个整数xx (1\le x\le2^{n+m}1≤x≤2)n + m)． 2 ^ n \ * 2 ^平方米n×2米是数独游戏的大小。dd是X和的方向，是“左”、“右”、“上”、“下”四个方向之一。Xx是行或列的索引。

输出描述:

对于每个测试用例:输出一个整数——字典序最小的2^n\乘以2^m2中dd方向的第xx行或第xx列的x和n×2米数独。注意，答案可能超过2^{64}-1264−1。考虑在c++中使用__int128_t，在Java或Kotlin中使用BigInteger，或在Python中使用int。