物理实验室中有一个长度为 $M$ 的环形装置，上面放有 $N$ 个磁铁，第 $i$ 个磁铁在原点沿顺时针方向走 $x_i$ 个单位长度的位置上。

每经过一个时刻，每一个磁铁都会独立地以 $p$ 的概率顺时针移动 $0.5$ 个单位长度，以 $1-p$ 的概率逆时针移动 $0.5$ 个单位长度。任意时刻，如果两个磁铁的位置相同了，它们就会吸在一起（大小变化忽略不计，可等效地看成一个磁铁），之后的运动会同步（也就是以 $p$ 的概率同时顺时针移动，以 $1-p$ 的概率同时逆时针移动）。

定义两个磁铁的距离为环上两个方向中距离的较小值。设 $f_i$ 表示经过 $i$ 个时刻之后，每一对磁铁（共 $\frac{n(n-1)}{2}$ 对）的距离之和的期望。给定 $L,R$，求出 $f_L,f_{L+1},\cdots,f_R$。答案对 $998244353$ 取模。

输入格式

第一行：五个整数 $N,M,p,L,R$。

第二行：$N$ 个整数 $x_1,x_2,\cdots,x_N$。

输出格式

一行，$R-L+1$ 个整数，分别表示 $f_L,f_{L+1},\cdots,f_R$。

样例数据

样例 1 输入

2 5 499122177 1 10
1 3

样例 1 输出

249561090 436731906 592707586 729186306 851042306 960712706 61476353 150964353 231884353 305069353

样例 2 输入

5 20 704273273 100 109
7 9 13 16 17

样例 2 输出

483503804 939740408 884209216 593653317 345573406 974131468 99837503 926658164 215247850 240109650

数据范围

对于所有数据，满足 $1\le N\le 10^5$，$3\le M\le 10^5$，$1<p<998244353$，$1\le L\le R\le 10^9$，$R-L+1\le 10^5$，$0\le x_i<M$。