乘 .筛 .积 (Sedge’s multiplication) 是定义在两个正整数序列 an, bm 和正整数 C 之间的一种运算。我们称 an, bm 关于正整数 p, q 的「C-乘筛积」为

$\sum_{1≤x≤n \vert 1≤y≤m \vert px+qy=C}{a_xb_y}$

敲钟人当然很能“筛”，牛瓜瓜却连 exgcd 都写不来，只好来问你：对于给定的 T 组 p, q，求 A, B 关于 p, q 的「C-乘筛积」模 998 244 353（一个质数）的值。

【输入格式】

从文件 sedge.in 中读入。

第一行三个整数 n, m, C。

第二行 n 个整数 a1, a2, · · · , an。

第三行 m 个整数 b1, b2, · · · , bm。

第四行一个整数 T ，表示询问组数。

接下来 T 行，每行两个整数 p, q，表示一组询问。

【输出格式】

输出到文件 sedge.out 中。

【样例 1 输入】

3 4 5

1 2 3

1 2 3 4

2

1 1

1 2

输出

16

5

T 行，每行一个整数，表示答案对 998 244 353 取模的值。

保证 1 ≤ n, m, T ≤ 3 × $10^5$; 1 ≤ p, q ≤ C ≤ 3 × $10^5$; 1 ≤ ai, bi < $2^{31}$。