题目描述

<第一乐章——Adagio>

乐团开始演奏末日的乐章。

<第二乐章——Sostenuto>

员工们逐渐丧失记忆，陶醉在乐团的演出之中。悠扬的乐声会唤醒心灵最深处的疯狂，促使员工们对眼前的一切活物发起攻击。

<第三乐章——Accelerando>

当乐章行进到这一步时，乐团加快了节奏，带领每一个部门走向毁灭。

<第四乐章——Stringendo>

当所有的演奏家聚集在一起时，乐团将会演奏除它们以外无人能够听闻的天籁之音。

<终章——Con Fuoco, Ma Non Troppo>

这首乐章将会穿透你的灵魂。

沉默乐团的演出进行到最后一个乐章，所有演奏家将共同协力，竭尽所能完成这场盛大的演出。沉默乐团中一共有 $n$ 位演奏家，第 $i$ 位演奏家的音域为 $1$ 到 $a_i$，并且他将连续演奏 $b_i$ 个音调，每次演奏他都可以从 $1$ 到 $a_i$ 中选取任意一个整数音调进行演奏。所有演奏家的所有音调演奏共同构成这一整个乐章的演出，我们可以发现根据每一位演奏家每个音调的不同选择，可以产生出难以计数的不同演出——我们认为如果两场演出中某一位演奏家某一次演奏的音调不同，则两场演出是不同的。

作为公司的主管，小D发现每一次演奏的音调如果大于一个阈值，那么这次演奏将带有强大的能量，而整个乐章的总能量等同于每一个演奏家演奏的带有能量的音调的数量的总和。具体来说，如果音调带有能量的阈值为 $k$，第 $i$ 位演奏家演奏的音调序列为 $t_{i_1},t_{i_2},t_{i_3},\dots, t_{i_{b_i}}$，首先应满足 $1\leq t_{i_j} \leq a_i$，而这段序列的能量则为 $e_i = \sum_{j=1}^{b_i}[ t_{i_j} \geq K]$，整个乐章的总能量则为

$$E = \sum_{i = 1}^n e_i = \sum_{i = 1}^n \sum_{j=1}^{b_i}[t_{i_j} \geq K] $$

现在，小D想知道，对于 $0$ 到 $m$ 中的每一个整数 $h$，整个乐章的能量 $E$ 恰好等于 $h$ 时的不同演出的方案数，这些数字可能过于巨大，你只需要给出它们对 $998244353$ 取模的结果。

输入

输入第一行包含三个正整数 $n(1 \leq n \leq 10^5)$，$m(1 \leq m \leq 10^5)$，$k(1 \leq k < 998244353)$，分别表示演奏家的数量，你要计算方案数的总能量范围，音调含有能量的阈值。

接下来一行包含 $n$ 个正整数 $a_i(1 \leq a_i < 998244353)$，表示每位演奏家的音域，

接下来一行包含 $n$ 个正整数 $b_i(1 \leq b_i < 998244353)$，表示每位演奏家演奏音调的数量。

输出

请输出一行 $m+1$ 个整数，表示总能量一定时演出的方案数对 $998244353$ 取模的结果。

样例

3 5 3
2 3 4
4 3 2

512 1792 2432 1600 512 64