The King of England, CauchySheep, has recently been studying chess. CauchySheep believes the chessboard is too small, so he has created his own set of rules:

In this problem, the chessboard is an $n \times m$ grid, where the cell in the $i$-th row ($1 \le i \le n$) and $j$-th column ($1 \le j \le m$) is denoted as $(i, j)$. To simplify the problem, there is only one piece on the board: a knight.

Now, CauchySheep places the knight at $(sx, sy)$ and it begins a random walk. Specifically, in each turn, if the knight is currently at $(x, y)$, it:

• Moves to $(x-2, y-1)$ with probability $p_1$.
• Moves to $(x-1, y-2)$ with probability $p_2$.
• Moves to $(x+1, y-2)$ with probability $p_3$.
• Moves to $(x+2, y-1)$ with probability $p_4$.
• Moves to $(x+2, y+1)$ with probability $p_5$.
• Moves to $(x+1, y+2)$ with probability $p_6$.
• Moves to $(x-1, y+2)$ with probability $p_7$.
• Moves to $(x-2, y+1)$ with probability $p_8$.

The game ends when the knight moves off the board.

Now, CauchySheep wants to know the expected number of turns until the game ends. CauchySheep can certainly solve this problem, but he wants to test you.

Input

The first line contains two positive integers $n, m$.

The second line contains $8$ positive integers $w_1, w_2, \dots, w_8$ used to calculate $p$, where $p_i = \frac{w_i}{\sum_{j=1}^8 w_j}$.

The third line contains a positive integer $q$, representing the number of queries.

The next $q$ lines each contain two positive integers $sx, sy$, representing the starting coordinates.

Output

For each query, output a single integer representing the answer modulo $998244353$. Specifically, if the answer is represented as an irreducible fraction $\frac{p}{q}$, you should output the value of $pq^{-1} \pmod{998244353}$.

Examples

Input 1

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

Output 1

1
332748119

Note 1

When $(sx, sy) = (2, 2)$, the knight will move off the board in one turn regardless of its move, so the answer is $1$.

When $(sx, sy) = (1, 1)$, the answer is $\frac{4}{3}$.

Input 2

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

Output 2

691709817
186871978
807608945
374193381

Note 2

I have a marvelous explanation, but the margin is too small to contain it.

Subtasks

For all test cases, $2 \le n, m \le 200$, $1 \le w_i \le 100$, $1 \le q \le nm$, and the queried $(sx, sy)$ are distinct.

There are six subtasks, with the following special constraints and scores:

• Subtask $1$ ($10$ points): $n, m \le 20$.
• Subtask $2$ ($10$ points): $n, m \le 50$.
• Subtask $3$ ($20$ points): $n, m \le 80$, $q=1$.
• Subtask $4$ ($20$ points): $n, m \le 80$.
• Subtask $5$ ($20$ points): $m$ is even.
• Subtask $6$ ($20$ points): No additional constraints.