D ToPTree

ToPTree 即 **To**oth**P**aste **Tree**，它的工作方式就如同挤牙膏——挤一下它才动一下。

你有 $n$ 个数组成的序列 $[a_1\sim a_n]$，初始时 $a_i=0$。 有 $q$ 次操作组成的操作序列 $A$，第 $i$ 次操作在所有可能的 $nN(n+1)$ 种操作之内均匀随机： - 在以下两种操作之中以一半的概率随机选择一种操作，作为这次操作。 - 随机选取满足条件的正整数 $l,r,x\ (1\le l\le r\le n,1\le x\le N)$，把 $[l,r]$ 区间内的数加上 $x$。 - 随机选取满足条件的正整数 $l,r,x\ (1\le l\le r\le n,1\le x\le N)$，把 $[l,r]$ 区间内的数改为 $x$。 - 容易发现每次操作共有 $nN(n+1)$ 种可能。 由于这棵树是 ToothPaste Tree，只有在你询问的时候，它才会执行与你这次询问有关且还没执行的操作。具体地，假设你依次询问了 $a_{p_1\sim p_m}$ 的值，则 - 询问 $a_{p_i}$ 时，把所有 $A$ 中与这个数有关的操作（即这次操作的 $[l,r]$ 包含 $p_i$）按时间顺序（即按 $A$ 中的顺序）执行了，并从 $A$ 中删除它们。然后输出 $a_{p_i}$ 当前的值。 > 比如 $A$ 中目前按顺序有以下四个操作，且 $a$ 中所有元素目前都是 $0$： > > 1. 给区间 $[2,3]$ 加一。 > 2. 给区间 $[3,4]$ 加一。 > 3. 把区间 $[2,4]$ 赋值为一。 > 4. 给区间 $[2,3]$ 加一。 > > 现在询问了 $a_2$ 的值，那么操作 $1,3,4$ 会被顺序执行，导致 $a_1\sim a_4$ 分别变为 $[0,2,2,1]$。因此 ToPTree 输出 $2$。操作序列变为： > > 1. 给区间 $[3,4]$ 加一。 > > 再询问 $a_3$ 的值，操作 $1$ 会被执行，导致操作序列变为空，并且 $a_1\sim a_4$ 变为 $[0,2,3,2]$，故输出 $3$。注意这个输出结果与按照顺序执行所有操作 $1\sim 4$ 得到的结果并不一致。 给定 $n,m,q,N$ 以及序列 $p$，ToPTree 一共会按询问顺序输出 $m$ 个值，求这 $m$ 次输出分别的期望，对 $998244353$ 取模。 （第一次询问之前，没有任何操作被执行了。）

第一行四个正整数 $n,m,q,N$。 接下来一行 $m$ 个正整数 $p_1\sim p_m$。

输出一行 $m$ 个非负整数，用空格隔开，为答案，对 $998244353$ 取模。

2 2 2 2
1 1

665496237 665496237

**【数据范围】** **本题采用捆绑测试。** 对于所有数据：$1\le n,N,q\le 9\times 10^8$，$1\le m\le 10^6$，$1\le p_i\le n$。详细数据范围如下： - Subtask #1 (4 pts): $n,m,q,N\le 3$。 - Subtask #2 (10 pts): $n,m,q,N\le 5$。 - Subtask #3 (3 pts): $n=1$，$m,q\le 123456$。 - Subtask #4 (3 pts): $q=1$，$m\le 123456$。 - Subtask #5 (12 pts): $m=1$，$q\le 123456$。 - Subtask #6 (27 pts): $n,m,q,N\le 50$。 - Subtask #7 (9 pts): $m,q\le 5000$。 - Subtask #8 (16 pts): $m,q\le 123456$。 - Subtask #9 (16 pts): 没有任何附加限制。