在台湾,许多数学老师设计棋盘和纸牌游戏来帮助学生掌握困难的数学概念。最近,一款纸牌游戏在中小学老师中火了起来,因为它能有效帮助学生理解除数和倍数的概念,同时对教师和学生来说也很有吸引力。
游戏规则如下。老师准备了 $$$n$$$ 不同的卡片,标记为从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 卡上写有一个整数值 $$$a_i$$$,整数 $$$a_1, a_2, \dots, a_n$$$ 严格按递增顺序排列。
有 $$$m$$$ 名学生参与游戏,标记为 $$$1$$$ 到 $$$m$$$。在游戏开始之前,每个学生都会收到 $$$n$$$ 卡的非空子集。没有两名学生共用一张牌,并且至少有一张牌未发。
让 $$$k$$$ 表示最初未发牌的数量。游戏由 $$$k$$$ 轮组成。在每一轮中,按顺序发生以下步骤:
- 老师统一随机选择一张剩余的未发牌并向所有学生展示。设 $$$c$$$ 为写在这张卡上的整数。
- 每个学生同时从自己的收藏中选择一张卡片。
- 所展示的卡牌的所有权确定如下:
- 在学生选择的所有卡片的值中,考虑那些可以被 $$$c$$$ 整除的值。
- 如果有一个或多个这样的值,则选择具有该值的卡片的学生 最小 可整除的价值赢得了翻开的牌并将其添加到他们的收藏中。
- 如果没有选择的牌的价值可以被 $$$c$$$ 整除,则翻开的牌将被丢弃(保持无主状态)。废弃的牌不会在后续回合中使用。
每个学生在整个游戏过程中都遵循相同的策略:
- 如果学生至少拥有一张价值可被 $$$c$$$ 整除的卡,则他们选择具有以下值的卡: 最小 值。
- 否则,他们选择带有 最小 他们拥有的价值。
假设所有学生在每一轮中都遵循此策略,请确定每个学生在游戏结束时预计拥有的卡片数量。
输入
第一行包含两个整数$$$n$$$和$$$m$$$,分别代表卡片数量和学生数量。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$,其中 $$$a_i$$$ 是第 $$$i$$$ 卡上的整数。
第三行包含 $$$n$$$ 整数 $$$b_1,b_2,\ldots,b_n$$$,其中 $$$b_i$$$ 描述游戏开始前第 $$$i$$$ 张牌的所有权:如果 $$$b_i \ne 0$$$,则该牌由第 $$$b_i$$$ 学生拥有,否则不发牌。
- $$$1 \leq m \lt n \leq 600$$$
- $$$1 \le a_i \le 10^{18}$$$
- $$$0 \leq b_i \leq m$$$
- $$$a_i \lt a_{i + 1}$$$ 对于所有 $$$1 \le i \lt n$$$。
- 至少有一个 $$$i$$$ 使得 $$$b_i = j$$$ 对于 $$$j = 0,1,\ldots,m$$$。
输出
在新行中打印 $$$m$$$ 数字,其中第 $$$i$$$ 数字代表第 $$$i$$$ 学生在游戏结束时预计拥有的卡片数量。
可以证明,每个答案都可以用有理数 $$$\frac{p}{q}$$$ 表示,其中 $$$q$$$ 不是 $$$998244353$$$ 的倍数。因此,您需要为每个数字打印 $$$p \times q^{-1}$$$ 模 $$$998244353$$$,其中 $$$q^{-1}$$$ 表示 $$$q$$$ 模 $$$998244353$$$ 的乘法逆元。
示例
输入复制
5 21 2 3 4 50 0 1 2 1
输出复制
499122179 499122179
输入复制
6 21 2 3 4 5 60 0 0 1 0 2
输出复制
831870297 166374061
输入复制
8 34 5 8 9 12 18 20 240 0 0 0 0 2 1 3
输出复制
332748120 2 665496239