题目描述

一个 $n\times m$ 数独是一张包含 $m\times n$ 个区域的网格，其中每个区域包含 $n\times m$ 个格子，因此一个 $n\times m$ 数独共有 $nm\times nm$ 个格子。 $n\times m$ 数独的每行、每列、每个区域都恰好包含 $1\sim nm$ 的所有整数。

对于某行或某列，从某个方向开始，依次列出这行（列）的 $nm$ 个数字，记得到的序列的第一个数为 $X$ ，则称这行（列）在这个方向上的 $X-sum$ 为此序列的前 $X$ 个数之和。

上图列出了一个 $4\times 2$ 数独及其所有 $X-sum$ 。例如，第 $7$ 行从右至左依次为 $[3,4,1,2,7,8,5,6]$ ，其中第一个数是 $3$ ，则第 $7$ 行的从右至左的 $X-sum$ 为 $3+4+1=8$ 。

给定正整数 $n,m$ ，一个方向 $d$ 和一个下标 $x$ ，求字典序最小的 $2^n\times 2^m$ 数独的第 $x$ 行（列）在方向 $d$ 上的 $X-sum$ 。

记数独 $a$ 的第 $i$ 行第 $j$ 列为 $a_{i,j}$ 。称数独 $a$ 的字典序小于数独 $b$ ，当且仅当存在 $x,y$ ，使得对于所有 $i < x$ 有 $a_{i,j}=b_{i,j}$ ，对于所有 $j < y$ 有 $a_{x,j}=b_{x,j}$ ，且 $a_{x,y} < b_{x,y}$ 。上图即为字典序最小的 $4\times 2$ 数独。

输入格式

本题有多组数据。第一行一个整数 $T$ ，表示数据组数。对于每组数据：

仅一行，依次为两个整数 $n,m$ ，一个字符串 $d$ 和一个整数 $x$ 。其中 $n,m$ 表示数独的大小为 $2^n\times 2^m$ ； $d$ 为 " $left$ "，" $right$ "，" $top$ " 和 " $bottom$ " 中的一个，分别表示从左至右、从右至左、从上至下、从下至上； $x$ 为行或列的下标。

输出格式

对于每组数据，输出一行一个整数，表示字典序最小的 $2^n\times 2^m$ 数独的第 $x$ 行（列）在方向 $d$ 上的 $X-sum$ 。
注意答案可能会超过 $\texttt{unsigned long long}$ 的范围，你可以使用 \texttt{__int128_t} 等数据类型。

数据范围

对于 $25\%$ 的数据， $n+m\le 8$ 。
另有 $5\%$ 的数据， $x=1$ 或 $x=2^{n+m}$ 。
另有 $15\%$ 的数据， $d$ 为 " $left$ " 或 " $right$ "， $x\le 2^n$ 。
另有 $15\%$ 的数据， $d$ 为 " $left$ " 或 " $right$ "。
另有 $20\%$ 的数据， $d$ 为 " $top$ " 或 " $bottom$ "， $x\le 2^m$ 。
另有 $10\%$ 的数据， $d$ 为 " $top$ " 或 " $bottom$ "。
对于 $100\%$ 的数据， $1\le T\le 10^5$ ， $1\le n,m\le 30$ ， $d$ 为 " $left$ "，" $right$ "，" $top$ " 和 " $bottom$ " 中的一个， $1\le x\le 2^{n+m}$ 。

输入样例 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