年度世界问答竞赛的决赛现在进入了高潮！

在本轮比赛中，题目将逐一提出，最先正确回答目标数量问题的选手将成为冠军。许多问题已经被提出并回答过了。目前各选手正确回答的问题数量可能不同，因此他们获胜所需额外正确回答的问题数量也可能不同。

裁判组精心准备的问题非常困难，且选手们拥有完全不同的专业领域。因此，对于每一道题，恰好只有一名选手能给出正确答案。

谁能成为冠军取决于提问的顺序。裁判组知道所有的问题以及谁能回答哪道题，但他们不知道剩余问题的顺序，因为这些问题已被随机打乱。为了帮助裁判组预测今年的冠军，请计算出使每位选手获胜的剩余问题顺序的数量。注意，在决出冠军后剩余未被使用的问题顺序也应被考虑在内。

输入格式

输入包含一个测试用例，格式如下：

$n \ m$ $a_1 \dots a_n$ $b_1 \dots b_n$

其中，$n$ 是选手人数，$m$ 是剩余问题的数量。$n$ 和 $m$ 均为满足 $1 \le n \le m \le 2 \times 10^5$ 的整数。选手编号为 $1$ 到 $n$。下一行包含 $n$ 个整数 $a_1, \dots, a_n$，表示选手 $i$ 能正确回答的剩余问题数量，满足 $\sum_{i=1}^n a_i = m$。最后一行包含 $n$ 个整数 $b_1, \dots, b_n$，表示选手 $i$ 还需要正确回答 $b_i$ 道题才能获胜。满足 $1 \le b_i \le a_i$。

输出格式

设 $c_i$ 为使选手 $i$ 成为冠军的问题顺序数量。输出 $n$ 行，每行包含一个整数。第 $i$ 行的数字应为 $c_i$ 对质数 $998\,244\,353 = 2^{23} \times 7 \times 17 + 1$ 取模的结果。注意 $\sum_{i=1}^n c_i = m!$ 成立。

样例

输入 1

2 4
2 2
1 2

输出 1

20
4

输入 2

4 6
1 1 2 2
1 1 1 2

输出 2

168
168
336
48

输入 3

4 82
20 22 12 28
20 22 7 8

输出 3

746371221
528486621
148054814
913602744