시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
15 초 | 1024 MB | 1 | 1 | 1 | 100.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 2 5 2
0 4 8 16 32
2 1 -1 1 1 1 2 4 2
0 4 8 48