시간 제한메모리 제한제출정답맞힌 사람정답 비율
15 초 1024 MB111100.000%

문제

Little Misha wants to change his IQ (initially he has $0$ IQ). He found $m$ types of courses on the internet. The $i$-th course type costs $c_i$ bitcoins, changes his IQ by $d_i$ ($d_i$ can be negative, that is, his IQ can decrease after a course), and there are $n_i$ different courses of $i$-th type. Authors of courses want to earn money, so $c_i \ge \lvert d_i \rvert$.

Misha wants to reach at least $k$ IQ (of course, $k$ can be negative). In order to achieve his goal, he will take a single course every day till some day. A course could be taken multiple times and each time it will affect Misha's IQ.

Now, he has $n$ bitcoins. He is wondering: in how many ways can he spend exactly $t$ bitcoins and reach at least $k$ IQ in the end, for each $1 \le t \le n$? Two ways are considered different if they differ in the number of days to study or in a course taken at some day (different courses of the same type are considered different as well).

입력

The first line contains a single integer $m$ ($0 < m < 100$): the number of types of courses.

Each of the next $m$ lines contains three integers $c_i$, $d_i$, $n_i$ ($0 < c_i < 10$, $\lvert d_i \rvert \le c_i$, $0 \le n_i \leq 10^4$).

And finally, the last line contains two integers $n$ and $k$ ($\lvert k \rvert \leq n \le 3 \cdot 10^4$, $n > 0$).

출력

Output $n$ integers, each on a separate line. The number on the $i$-th line should be the number of ways to spend exactly $i$ bitcoins and obtain at least $k$ IQ. Since these numbers can be large, output them modulo $998\,244\,353$.

예제 입력 1

1
1 1 2
5 2

예제 출력 1

0
4
8
16
32

예제 입력 2

2
1 -1 1
1 1 2
4 2

예제 출력 2

0
4
8
48