题目描述

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

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

由于子弹的生产都是 $m$ 颗一盒生产的，而且生产质量是一致的，所以可以认为存在一个长度为 $m$ 的序列 $p_i'$，使得对于轮盘里的 $n$ 颗子弹，有：$p_i=p_{i\bmod 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(\varnothing)$，以及 $f(S_i),i=1,2\dots q+t$，但是小 X 还要去解决其他的问题，所以他找到了你。

你需要告诉小 X $f(\varnothing)$， $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(\varnothing)$，接下来第 $i+1$ 行为 $n\times f(S_i)$ 。

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

5
748683269
6
5

提示

样例解释

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

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

$S_1=\{(0,\dfrac{1}{2})\}$，替换后的序列为 $\dfrac{1}{2},\dfrac{1}{2},0$，答案为 $(1\times \dfrac{1}{2}+2\times \dfrac{1}{4}+3\times \dfrac{1}{4})+(1\times \dfrac{1}{2}+2\times \dfrac{1}{2})+1=\dfrac{17}{4}$，$\dfrac{17}{4}\equiv 748683269\pmod {998244353}$。

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

$S_3=S_1\cup S_2=\{(0,\dfrac{1}{2}),(1,1)\}$，替换后的序列为 $\dfrac{1}{2},1,0$，答案为 $(1\times \dfrac{1}{2}+3\times \dfrac{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\neq j,x_i\neq 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）：无特殊限制。