D. Divisor Card Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In Taiwan, many mathematics teachers design board and card games to help students grasp difficult mathematical concepts. Recently, a particular card game has gone viral among elementary and middle school teachers because it effectively helps students understand the concepts of divisors and multiples, while also being highly engaging for both teachers and students.

The rules of the game are as follows. The teacher prepares $$$n$$$ distinct cards, labeled from $$$1$$$ to $$$n$$$. The $$$i$$$-th card has an integer value $$$a_i$$$ written on it, and the integers $$$a_1, a_2, \dots, a_n$$$ are in a strictly increasing order.

There are $$$m$$$ students labeled from $$$1$$$ to $$$m$$$ participating in the game. Before the game begins, each student receives a nonempty subset of the $$$n$$$ cards. No two students share any card, and at least one card remains undealt.

Let $$$k$$$ denote the number of undealt cards initially. The game consists of $$$k$$$ rounds. In each round, the following steps occur in order:

  1. The teacher selects one of the remaining undealt cards uniformly at random and reveals it to all students. Let $$$c$$$ be the integer written on this card.
  2. Each student simultaneously chooses exactly one card from their own collection.
  3. The ownership of the revealed card is determined as follows:
    • Among the values of all cards chosen by the students, consider those that are divisible by $$$c$$$.
    • If there are one or more such values, the student who selected a card with the smallest divisible value wins the revealed card and adds it to their collection.
    • If no chosen cards have value divisible by $$$c$$$, the revealed card is discarded (remains unowned). Discarded cards are not used in subsequent rounds.

Each student follows the same strategy throughout the game:

  • If the student owns at least one card whose value is divisible by $$$c$$$, they choose the card with the smallest value.
  • Otherwise, they choose the card with the smallest value among those they own.

Assuming that all students follow this strategy in every round, determine the expected number of cards that each student will own at the end of the game.

Input

The first line contains two integers $$$n$$$ and $$$m$$$, representing the number of cards and the number of students, respectively.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$, where $$$a_i$$$ is the integer on the $$$i$$$-th card.

The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$, where $$$b_i$$$ describes the ownership of the $$$i$$$-th card before the game begins: it is owned by the $$$b_i$$$-th student if $$$b_i \ne 0$$$, and is undealt otherwise.

  • $$$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}$$$ for all $$$1 \le i \lt n$$$.
  • There is at least one $$$i$$$ such that $$$b_i = j$$$ for $$$j = 0,1,\ldots,m$$$.
Output

Print $$$m$$$ numbers in a new line, where the $$$i$$$-th number represents the expected number of cards the $$$i$$$-th student will own at the end of the game.

It can be proven that each answer can be represented by a rational number $$$\frac{p}{q}$$$ where $$$q$$$ is not a multiple of $$$998244353$$$. Therefore, you are asked to print $$$p \times q^{-1}$$$ modulo $$$998244353$$$ for each number, where $$$q^{-1}$$$ means the multiplicative inverse of $$$q$$$ modulo $$$998244353$$$.

Examples
Input
5 2
1 2 3 4 5
0 0 1 2 1
Output
499122179 499122179
Input
6 2
1 2 3 4 5 6
0 0 0 1 0 2
Output
831870297 166374061
Input
8 3
4 5 8 9 12 18 20 24
0 0 0 0 0 2 1 3
Output
332748120 2 665496239