很久很久以前，有一个棋盘加入了 UOJ 群。

这天，在它讨论“一个棋盘应该怎么对偶”的时候一不小心被删除了，变成了量子态的棋盘。

突然间，它发现本来在它身上记录的东西全都变成量子态了。这让它的主人——著名的物理专家 Picks 博士非常烦恼：要知道这个棋盘可以他非常重要的试验道具。

于是他来找你帮忙尽可能地还原这个棋盘。

已知这个棋盘的大小是 $n\times m$ ，每一个格子的权值都是 $1$ 或者 $-1$ 。这个棋盘左上角格子的上方是入口，下边界和右边界是出口。

当 Picks 博士从左上角上方放入一个小球的时候，这个小球在这个棋盘中会以如下的方式运行：

如果当前小球所在的格子的权值是 $1$，那么小球将会从这个格子的右边界出去，否则它会从这个格子的下边界出去。在小球离开这个格子之后，这个格子的权值会变成原来的相反数，即 $1$ 变成 $-1$，$-1$ 变成 $1$。

Picks 博士的实验中的一步是这样的：他会依次往棋盘的左上角放入$K$个小球，每一个小球都是在前一个小球离开棋盘后再放入。当小球离开棋盘后，它会直接掉到地上。为了避免满地小球的情况， Picks 在一些出口下面挂了篮子，如果小球从挂了篮子的出口处离开棋盘，那么它会被篮子接住，否则它还是会掉到地上。

Picks 博士进行了 $Q$ 这样的试验，为了避免麻烦，任意两次实验的棋盘大小，放入小球个数，篮子的位置都是完全一样，他只更改了初始棋盘上的数字。但是因为实验结果被打杂的 jiry_2 吃掉了，所以他现在只记得第 $i$ 次试验接到的小球数目在区间 $[L_i,R_i]$ 内。

现在，Picks 博士告诉了你棋盘的大小，放入小球的个数，篮子的位置，以及每一次实验的 $L_i$ 和 $R_i$，他想要拜托你算出来每一次试验有多少种可能的棋盘是满足条件的。

输入格式

第一行是三个整数 $n,m,K$ ，分别表示棋盘的行数、列数以及每一次实验放入的小球个数。保证有 $n,m\ge 1$ 和 $K\ge 0$。

第二行包含了一个长度为 $n$ 的 01 串，第 $i$ 个字符是 1 表示第 $i$ 行的最右端挂了一个篮子，否则表示没有篮子。

第三行包含了一个长度为 $m$ 的 01 串，第 $i$ 个字符是 1 表示第 $i$ 列的最下端挂了一个篮子，否则表示没有篮子。

第四行包含了一个正整数 $Q$，表示实验的次数。

接下来 $Q$ 行，每行是两个整数 $L_i,R_i(0\le L_i\le R_i\le K)$ 表示 Picks 博士提供的试验的结果。

输出格式

共$Q$行，对于每一次试验你都需要输出一个整数，表示满足实验结果的不同棋盘的个数。两个棋盘时不同的当且仅当存在$i,j$使得两个棋盘第 $i$ 行第 $j$ 列的权值不同。

答案可能很大，你只需要输出答案对 $998244353（7\times 17\times 2^{23}+1$，一个质数$）$ 取模后的结果。

样例一

input

3 3 5
111
111
2
0 3
4 5

output

0
512

explanation

可以发现，无论棋盘时什么样的，篮子总是可以接到所有的小球，所以对于所有可能的 $2^{nm}=512$ 种方案，Picks都能接到 $5$ 个小球。

样例二

input

1 2 2
1
10
3
0 0
1 1
2 2

output

0
2
2

explanation

一共有四种棋盘：

1. 初始棋盘是 $1,1$。第一个小球会从棋盘右边界运行出去被篮子接到。此时棋盘变成了 $-1,-1$，第二个小球会从第一列的下方运行出去被篮子接到，此时棋盘变成了 $1,-1$。
2. 初始棋盘是 $1,-1$。第一个小球会从棋盘第二列的下方运行出去掉到地上。此时棋盘变成了 $-1,1$，第二个小球会从第一列的下方运行出去被篮子接到，此时棋盘变成了 $1,1$。
3. 初始棋盘是 $-1,1$。第一个小球会从棋盘第一列的下方运行出去被篮子接到。此时棋盘变成了 $1,1$，第二个小球会从棋盘的右边界运行出去被篮子接到，此时棋盘变成了 $-1,-1$。
4. 初始棋盘是 $-1,-1$。第一个小球会从棋盘第一列的下方运行出去被篮子接到。此时棋盘变成了 $1,-1$，第二个小球会从第二列的下方运行出去掉到地上，此时棋盘变成了 $-1,1$。

所以接到两个球和接到一个球的方案各有两个。

样例三

input

4 4 15
1011
1000
2
1 6
7 15

output

29696
35840

限制与约定

时间限制：$2\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载