题目描述

英国之王 CauchySheep 最近在研究国际象棋。CauchySheep 认为棋盘太小了，所以他自创了一套规则：

在本题中，国际象棋的棋盘是一个 $n \times m$ 的网格，第 $i$ ($1 \le i \le n$) 行第 $j$ ($1 \le j \le m$) 个格子简记为 $(i, j)$。为了简化问题，棋盘上只有一枚棋子：骑士。

现在 CauchySheep 将骑士放在 $(sx, sy)$，然后开始随机游走。具体地，每个回合，假设骑士当前在 $(x, y)$，则它：

• 有 $p_1$ 的概率走到 $(x-2, y-1)$。
• 有 $p_2$ 的概率走到 $(x-1, y-2)$。
• 有 $p_3$ 的概率走到 $(x+1, y-2)$。
• 有 $p_4$ 的概率走到 $(x+2, y-1)$。
• 有 $p_5$ 的概率走到 $(x+2, y+1)$。
• 有 $p_6$ 的概率走到 $(x+1, y+2)$。
• 有 $p_7$ 的概率走到 $(x-1, y+2)$。
• 有 $p_8$ 的概率走到 $(x-2, y+1)$。

当骑士走出棋盘时，游戏就结束了。

现在 CauchySheep 想要知道游戏期望经过多少个回合结束。CauchySheep 当然会做这个题，但是他想考考你。

---

输入格式

从标准输入读入数据。

• 第一行两个正整数 $n, m$。
• 第二行 $8$ 个正整数 $w_1, w_2, \cdots, w_8$ 用于计算 $p$，$$p_i = \frac{w_i}{\sum_{j=1}^8 w_j}.$$
• 第三行一个正整数 $q$ 表示询问个数。
• 接下来 $q$ 行，每行两个正整数 $sx, sy$ 表示起始坐标。

---

输出格式

输出到标准输出中。

对于每个询问，输出一行一个整数表示答案在模 $998244353$ 意义下的值。具体地，假设答案化成既约分数后是 $\frac{p}{q}$，则你只需要输出 $p \cdot q^{-1} \bmod 998244353$ 的值即可。

---

样例 1

输入

3 3
1 1 1 1 1 1 1 1
2
2 2
1 1

输出

1
332748119

解释

• 当 $(sx, sy) = (2, 2)$ 时，骑士不管怎么走都会一步走出棋盘，答案为 $1$。
• 当 $(sx, sy) = (1, 1)$ 时，答案为 $\frac{4}{3}$。

---

样例 2

输入

8 8
1 2 3 4 5 6 7 8
4
1 2
3 4
5 6
7 8

输出

691709817
186871978
807608945
374193381

---

提示 我有一个绝妙的解释，可是这里地方太小，写不下。

数据范围与提示

对于所有数据，满足 $2 \le n, m \le 200$，$1 \le w_i \le 100$，$1 \le q \le nm$，询问的 $(sx, sy)$ 互不相同。

共有六个子任务，每个子任务的特殊限制和分值如下：

• 子任务 1（10 分）：$n, m \le 20$；
• 子任务 2（10 分）：$n, m \le 50$；
• 子任务 3（20 分）：$n, m \le 80$，$q = 1$；
• 子任务 4（20 分）：$n, m \le 80$；
• 子任务 5（20 分）：$m$ 是偶数；
• 子任务 6（20 分）：没有附加限制。