A roulette wheel has $n$ bullets, numbered $0, 1, \dots, n-1$. Each bullet $i$ has a misfire probability $p_i$, meaning if bullet $i$ is fired, it misfires with probability $p_i$ and fires successfully with probability $1 - p_i$.

The rules of the roulette game are as follows: a bullet is chosen uniformly at random from the $n$ bullets to start the game. In each round, one bullet is fired. If the bullet fires successfully, the game ends. Otherwise, the wheel rotates $d$ positions, and the game proceeds to the next round, where the next bullet to be fired is $(i+d) \bmod n$. Little X wants to know the expected number of rounds until the game ends.

Since bullets are produced in batches of $m$ with consistent quality, there exists a sequence $p'_i$ of length $m$ such that for the $n$ bullets in the wheel, $p_i = p_{i \bmod m}'$ ($i = 0, 1, \dots, n-1$).

To make the game more interesting, Little X has found $q$ special bullets, which he will use to replace some of the bullets in the wheel. Little X will formally describe this replacement process.

Each of Little X's special bullets can be represented as a tuple $(x, y)$, meaning this bullet replaces the bullet at position $x$ in the wheel, changing its misfire probability to $y$.

Each replacement operation is a set of tuples $S$ (it is guaranteed that all $x$ in the tuples $(x, y)$ within $S$ are distinct). For all $(x, y) \in S$, Little X replaces the bullet at position $x$ in the sequence, changing its misfire probability to $y$.

For a set of tuples $S$ (i.e., one replacement operation), let $f(S)$ be the expected number of rounds until the game ends using the bullets after the replacement.

Little X generates $q+t$ replacements as follows:

• The first $q$ replacements are generated as: the $i$-th replacement is $S_i = \{(x_i, y_i)\}$.
• The subsequent $t$ replacements are generated as: the $(q+j)$-th replacement is the result of merging two previously defined replacements that have not been selected before. Specifically, choosing the $a_j$-th and $b_j$-th replacements ($a_j, b_j < q+j$), the $(q+j)$-th replacement is $S_{q+j} = S_{a_j} \cup S_{b_j}$.

Little X wants to find $f(\emptyset)$ and $f(S_i)$ for $i = 1, 2, \dots, q+t$. However, Little X has other problems to solve, so he has come to you.

You need to tell Little X the results of $f(\emptyset)$ and $f(S_i)$ ($i = 1, 2, \dots, q+t$) multiplied by $n$. Since the results may be large and not necessarily integers, you only need to output the results modulo $998244353$.

Input

The first line contains five integers $n, m, d, q, t$.

The second line contains $m$ integers, where the $i$-th integer is $p'_{i-1}$.

The next $q$ lines each contain two integers $x_i, y_i$, representing $S_i = \{(x_i, y_i)\}$.

The next $t$ lines each contain two integers $a_i, b_i$, representing $S_{i+q} = S_{a_i} \cup S_{b_i}$.

Output

A total of $1 + q + t$ lines, where the first line is $n \times f(\emptyset)$, and the $(i+1)$-th line is $n \times f(S_i)$.

Examples

Input 1

3 3 1 2 1
1 499122177 0
0 499122177
1 1
1 2

Output 1

5
748683269
6
5

Note

$\frac{1}{2} \equiv 499122177 \pmod{998244353}$, so the misfire probabilities of the three bullets can be considered as $1, \frac{1}{2}, 0$.

For $f(\emptyset)$, the sequence is $1, \frac{1}{2}, 0$. The expected number of rounds for the first bullet is $2 \times \frac{1}{2} + 3 \times \frac{1}{2} = \frac{5}{2}$. The expected number of rounds for the second bullet is $1 \times \frac{1}{2} + 2 \times \frac{1}{2} = \frac{3}{2}$. The expected number of rounds for the third bullet is $1$. The final answer is $\frac{5}{2} + \frac{3}{2} + 1 = 5$.

$S_1 = \{(0, \frac{1}{2})\}$, the sequence after replacement is $\frac{1}{2}, \frac{1}{2}, 0$. The answer is $(1 \times \frac{1}{2} + 2 \times \frac{1}{4} + 3 \times \frac{1}{4}) + (1 \times \frac{1}{2} + 2 \times \frac{1}{2}) + 1 = \frac{7}{4}$, and $\frac{7}{4} \equiv 748683269 \pmod{998244353}$.

$S_2 = \{(1, 1)\}$, the sequence after replacement is $1, 1, 0$. The answer is $3 + 2 + 1 = 6$.

$S_3 = S_1 \cup S_2 = \{(0, \frac{1}{2}), (1, 1)\}$, the sequence after replacement is $\frac{1}{2}, 1, 0$. The answer is $(1 \times \frac{1}{2} + 3 \times \frac{1}{2}) + 2 + 1 = 5$.

Constraints

For all data: $1 \le d \le n \le 10^{16}$, $m \le 5000$. $1 \le q, t \le 10^5$, $0 \le x_i < n$ and $\forall i \ne j, x_i \ne x_j$, $0 \le p'_i, y_i < 998244353$, $1 \le a_i, b_i < i+q$ and it is guaranteed that all $a_i, b_i$ are distinct. It is guaranteed that $\gcd(d, n) = 1$, and for any query, the product of the misfire probabilities of all bullets modulo $998244353$ is not equal to $1$.

• Subtask 1 (10 pts): $1 \le q, t, n \le 10^3$.
• Subtask 2 (15 pts): $1 \le n \le 10^6$.
• Subtask 3 (30 pts): $d = 1$.
• Subtask 4 (20 pts): $q = t = 0$.
• Subtask 5 (25 pts): No special restrictions.