In a physics laboratory, there is a circular device of length $M$ with $N$ magnets placed on it. The $i$-th magnet is located at a position $x_i$ units clockwise from the origin.

At each time step, every magnet independently moves $0.5$ units clockwise with probability $p$, and $0.5$ units counter-clockwise with probability $1-p$. If at any time two magnets reach the same position, they stick together (the change in size is ignored, and they can be effectively treated as a single magnet). Their subsequent movement is synchronized (i.e., they move clockwise together with probability $p$ and counter-clockwise together with probability $1-p$).

Define the distance between two magnets as the smaller of the two distances along the circle. Let $f_i$ be the expected value of the sum of distances between every pair of magnets (there are $\frac{n(n-1)}{2}$ such pairs) after $i$ time steps. Given $L$ and $R$, calculate $f_L, f_{L+1}, \dots, f_R$. The answers should be taken modulo $998244353$.

Input

The first line contains five integers $N, M, p, L, R$. The second line contains $N$ integers $x_1, x_2, \dots, x_N$.

Output

A single line containing $R-L+1$ integers, representing $f_L, f_{L+1}, \dots, f_R$ respectively.

Examples

Input 1

2 5 499122177 1 10
1 3

Output 1

249561090 436731906 592707586 729186306 851042306 960712706 61476353 150964353 231884353 305069353

Input 2

5 20 704273273 100 109
7 9 13 16 17

Output 2

483503804 939740408 884209216 593653317 345573406 974131468 99837503 926658164 215247850 240109650

Constraints

For all data, $1\le N\le 10^5$, $3\le M\le 10^5$, $1