题目描述

一个有 $n$ 颗子弹的轮盘，子弹依次编号为 $0, 1, \dots, n-1$，每一颗子弹有一个卡壳概率 $p_i$，表示如果即将激发的子弹是第 $i$ 颗，那么它有 $p_i$ 的概率卡壳不能被打出，有 $1 - p_i$ 的概率成功打出。

轮盘赌游戏的规则如下：均匀随机地从 $n$ 颗子弹中选择一颗子弹开始进行轮盘赌，每一轮都会激发一颗子弹，假设某一轮激发第 $i$ 颗子弹，如果子弹成功打出了，那么游戏结束；否则轮盘会向后旋转 $d$ 颗子弹，游戏进入下一轮，也就是即将激发的子弹会变成第 $(i+d) \mod n$ 颗。小 X 想要知道轮盘赌游戏结束轮数的期望。

由于子弹的生产都是 $m$ 颗一盒生产的，而且生产质量是一致的，所以可以认为存在一个长度为 $m$ 的序列 $p'*i$，使得对于轮盘里的 $n$ 颗子弹，有：$p_i = p*{i \mod m}'$, $i = 0, 1, \dots, n-1$。

为了增加游戏的乐趣，小 X 找到了 $q$ 枚特殊的子弹，他将会用这些子弹替换掉轮盘中的某一些子弹。小 X 将形式化地告诉你这个替换的过程。

小 X 的每一颗特殊子弹都可以看作是一个二元组 $(x, y)$，表示这一颗子弹可以替换掉轮盘中的编号为 $x$ 子弹，让这一颗子弹的卡壳概率变成 $y$。

小 X 的每一次替换都可以看作是一个二元组集合 $S$（保证 $S$ 中的所有二元组 $(x, y)$ 中 $x$ 互不相同），对于所有的 $(x, y) \in S$，小 X 会将序列上的编号为 $x$ 颗子弹替换掉，让这颗子弹的卡壳概率变成 $y$。

而对于一个二元组集合 $S$（也就是一次替换），记 $f(S)$ 为用完成替换之后的子弹进行轮盘赌游戏，游戏结束轮数的期望。

小 X 会以如下方式生成 $q+t$ 个替换：

• 其中前 $q$ 个替换的生成方式如下：第 $i$ 个替换为 $S_i = {(x_i, y_i)}$ 。
• 后 $t$ 个替换的生成方式如下：第 $q+j$ 个替换是给定两个编号比它小且没有被选择过的替换，将其合并得到的结果。具体的，选择第 $a_j$ 和 $b_j$ 个替换（$a_j, b_j < q+j$），那么有第 $q+j$ 个替换为 $S_{q+j} = S_{a_j} \cup S_{b_j}$。

小 X 想要求出 $f(\emptyset)$，以及 $f(S_i), i = 1, 2, \dots, q+t$，但是小 X 还要去解决其他的问题，所以他找到了你。

你需要告诉小 X $f(\emptyset)$， $f(S_i)$（$i = 1, 2, \dots, q+t$）乘 $n$ 之后的结果，由于结果可能较大且不一定为整数，所以你只需要输出其对 $998244353$ 取模后的结果。

输入格式

第一行输入五个数 $n, m, d, q, t$。

第二行输入 $m$ 个数，其中第 $i$ 个数为 $p'_{i-1}$。

接下来的 $q$ 行，每行两个数 $x_i, y_i$，表示 $S_i = {(x_i, y_i)}$。

接下来的 $t$ 行，每行两个数 $a_i, b_i$，表示 $S_{i+q} = S_{a_i} \cup S_{b_i}$。

输出格式

共 $1 + q + t$ 行，其中第一行为 $n \times f(\emptyset)$，接下来第 $i + 1$ 行为 $n \times f(S_i)$ 。

样例

样例输入 1

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

样例输出 1

5
748683269
6
5

样例解释

$\frac{1}{2} \equiv 499122177 \pmod{998244353}$，所以可以认为三颗子弹的卡壳概率为 $1, \frac{1}{2}, 0$。

对于 $f(\emptyset)$，序列为 $1, \frac{1}{2}, 0$，第一颗子弹进行的期望轮数为 $2 \times \frac{1}{2} + 3 \times \frac{1}{2} = \frac{5}{2}$，第二颗子弹进行的期望轮数为 $1 \times \frac{1}{2} + 2 \times \frac{1}{2} = \frac{3}{2}$，第三颗子弹的期望轮数为 $1$，最终答案为 $\frac{5}{2} + \frac{3}{2} + 1 = 5$。

$S_1 = {(0, \frac{1}{2})}$，替换后的序列为 $\frac{1}{2}, \frac{1}{2}, 0$，答案为 $(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}$，$\frac{7}{4} \equiv 748683269 \pmod{998244353}$。

$S_2 = {(1, 1)}$，替换后的序列为 $1, 1, 0$，答案为 $3 + 2 + 1 = 6$。

$S_3 = S_1 \cup S_2 = {(0, \frac{1}{2}), (1, 1)}$，替换后的序列为 $\frac{1}{2}, 1, 0$，答案为 $(1 \times \frac{1}{2} + 3 \times \frac{1}{2}) + 2 + 1 = 5$。

数据范围

对于所有数据满足：$1 \le d \le n \le 10^{16}$，$m \le 5000$。$1 \le q, t \le 10^5$，$0 \le x_i < n$ 且 $\forall i \ne j, x_i \ne x_j$，$0 \le p'_i, y_i < 998244353$，$1 \le a_i, b_i < i+q$ 且保证所有的 $a_i, b_i$ 均不相同，数据保证 $\gcd(d, n) = 1$，且对于任何询问，所有子弹被卡壳的概率之积对 $998244353$ 取模不等于 $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）：无特殊限制。