有个$n\times m$的矩阵，行编号为$0\dots n-1$，列编号为$0\dots m-1$，第$i$行第$j$列一开始为$im+j$.

现在支持三种操作：交换两行，交换两列，或者交换某两个位置。

求进行完$q$次操作后矩阵的形态。

输入格式

为了减小输入规模，本题采取以下方式读入：

第一行四个数$n,m,q,seed$表示行数，列数，操作数，随机种子。

生成器代码如下：

uint64_t seed;
uint64_t next(){ //xorshift64
    seed^=seed<<13;
    seed^=seed>>7;
    seed^=seed<<17;
    return seed;
}

接下来一个长度为$q$的串$s$，表示$q$次操作分别的类型。

对于第$i$次操作，如果$s_i$是r，则操作为交换第$r_1,r_2$行，如果是c则为交换第$c_1,c_2$列，f则为交换$(r_1,c_1),(r_2,c_2)$，这些变量按顺序分别是调用next()的返回值对$n$或$m$取模后的值。

输出格式

为了减小输出规模，设$a_{i,j}$为最后矩阵第$i$行第$j$列的值，只需要输出$(\sum_{i,j} a_{i,j}17^i19^j)\bmod 998244353$之后的值.

样例一

input

3 5 3 114514
crf

output

382914571

explanation

操作序列为：

c 3 0
r 2 1
f 1 2 2 2

最终矩阵为：

3 1 2 0 4
13 11 7 10 14
8 6 12 5 9

样例二

见下发文件。

数据范围与提示

对于$100\%$的数据，$1\leq n,m\leq 5000,1\leq q\leq 10^6,0\leq seed\lt 2^{64}$.