#P18413. Courses

Courses

Courses

标准输入、标准输出。

小 Misha 想改变自己的 IQ。他最初的 IQ 为 00。他在网上找到了 mm 类课程:第 ii 类课程的每门课程花费 cic_i 个比特币,使 IQ 改变 did_i(did_i 可以为负,也就是 IQ 可能降低),这一类共有 nin_i 门不同的课程。课程作者希望赚钱,因此 ci≥∣di∣c_i\ge|d_i|。

Misha 想让最终 IQ 至少为 kk,其中 kk 也可以为负。为此,他每天学习一门课程,并在某一天结束学习。**同一门课程可以重复学习,每次都会使 IQ 发生相应变化。**IQ 允许为负,达标条件在学习结束时检查。

现在他有 nn 个比特币。请对每个 1≤t≤n1\le t\le n,求他恰好花费 tt 个比特币、结束时 IQ 至少为 kk 的学习方案数。

若两种方案的学习天数不同,或某一天所选的具体课程不同,就认为它们不同;同一类中的不同课程也算不同的选择。

输入格式

第一行一个整数 mm(0<m<1000<m<100),表示课程类型数量。

接下来 mm 行,每行三个整数 ci,di,nic_i,d_i,n_i,满足

$$0<c_i<10,\qquad |d_i|\le c_i,\qquad 0\le n_i\le10^4.$$

最后一行两个整数 n,kn,k,满足 ∣k∣≤n≤3⋅104|k|\le n\le3\cdot10^4 且 n>0n>0。

输出格式

输出 nn 个整数,每行一个。第 ii 行表示恰好花费 ii 个比特币且最终 IQ 至少为 kk 的方案数,对 998244353998244353 取模。

样例 1

1
1 1 2
5 2
0
4
8
16
32

样例 2

2
1 -1 1
1 1 2
4 2
0
4
8
48