物理实验室中有一个长度为 $ 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 $。
| 子任务编号 | 分值 | $ N\le $ | $ M\le $ | $ R\le $ | $ R-L+1\le $ |
|---|---|---|---|---|---|
| 1 | 5 | $ 7500 $ | $ 7500 $ | $ M $ | $ 10^5 $ |
| 2 | 5 | $ 10^5 $ | $ 7500 $ | $ M $ | $ 10^5 $ |
| 3 | 10 | $ 10^5 $ | $ 7500 $ | $ 10^9 $ | $ 1 $ |
| 4 | 15 | $ 10^5 $ | $ 7500 $ | $ 10^9 $ | $ 10^5 $ |
| 5 | 15 | $ 10^5 $ | $ 5\times 10^4 $ | $ M $ | $ 1 $ |
| 6 | 15 | $ 10^5 $ | $ 5\times 10^4 $ | $ M $ | $ 10^5 $ |
| 7 | 5 | $ 10^5 $ | $ 5\times 10^4 $ | $ 10^9 $ | $ 1 $ |
| 8 | 10 | $ 10^5 $ | $ 10^5 $ | $ 10^9 $ | $ 1 $ |
| 9 | 10 | $ 10^5 $ | $ 5\times 10^4 $ | $ 10^9 $ | $ 5\times 10^4 $ |
| 10 | 10 | $ 10^5 $ | $ 10^5 $ | $ 10^9 $ | $ 10^5 $ |