K. Lottery
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a lottery that is going to happen and $$$n$$$ ($$$1 \le n \le 10^6$$$) people have already bought one or more lottery tickets: the $$$i$$$th person has bought $$$t_i$$$ ($$$1 \le t_i \le 5$$$) lottery tickets. There will be $$$m$$$ ($$$1 \le m \le \min{\left( 100, n \right)}$$$) draws. In the $$$j$$$-th ($$$1 \le j \le m$$$) draw:

  • a ticket $$$T$$$ is selected uniformly randomly among all the remaining tickets;
  • the person $$$P$$$ who has bought the ticket $$$T$$$ will be declared as the winner of the $$$m-j+1$$$-th prize;
  • and all of person $$$P$$$'s tickets are removed from the lottery.

Alice is the last (that is, the $$$n+1$$$-th) ticket buyer, and she wants to win the $$$k$$$-th prize ($$$1 \le k \le m$$$). Alice can buy between $$$1$$$ to $$$l$$$ ($$$1 \le l \le 2000$$$) lottery tickets (inclusive range). She wants to know, for each $$$x \in \{ 1, \dots, l \}$$$, what the probability for winning the $$$k$$$-th prize is if she buys exactly $$$x$$$ tickets.

Alice has figured out that the probability $$$f(x)$$$ of winning the first prize is given by $$$$$$ f(x) = \sum_{\substack{A \subseteq \{ 1, \dots, n\} \\ |A| \le m - 1}} \left( -1 \right)^{m - 1 - |A|} {{n - |A|}\choose{m - 1 - |A|}} \left( \frac{x}{x + \sum_{j \not\in A} t_j} \right) $$$$$$

Alice has asked you to figure out the rest.

Input

The first line contains four space-separated integers $$$n, m, k, l$$$. The next line contains $$$n$$$ space-separated integers $$$t_1, \dots, t_n$$$.

Output

For each $$$i \in \{1, \dots, l\}$$$, the probability that Alice wins the $$$k$$$-th prize if she buys $$$i$$$ tickets can be represented by $$$\frac{a_i}{b_i}$$$, where $$$a_i$$$ and $$$b_i$$$ are some integers.

The output will consist of $$$l$$$ lines. The $$$i$$$-th line will contain the unique integer $$$c_i$$$ satisfying $$$0 \le c_i \lt 998244353$$$ and $$$a_i \equiv b_i c_i \pmod{998244353}$$$.

Example
Input
3 1 1 4
1 2 3
Output
855638017
748683265
332748118
199648871