Description

年度世界知识竞赛总决赛现已进入高潮！

在这一轮中，问题逐个提出，最先正确回答到目标数量的选手将成为冠军。许多问题已经被提出并回答。目前每位选手正确回答的问题数量可能不同，因此为了获胜需要额外正确回答的问题数量也可能不同。

裁判团队精心设计的问题非常困难，选手们的专长领域完全不同。因此，对于每个问题，恰好有一位选手能找到正确答案。

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

Input Format

输入由单个测试用例组成，格式如下。

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

Output Format

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

2 4
2 2
1 2

20
4

4 6
1 1 2 2
1 1 1 2

168
168
336
48

4 82
20 22 12 28
20 22 7 8

746371221
528486621
148054814
913602744