Polina 买了 $n$ 个指甲贴片，在每个贴片上涂了她 $n$ 种不同颜色指甲油中的一种（她可以在多个指甲贴片上使用相同的指甲油，也可以完全不使用某些颜色的指甲油），并将它们排成一排放在桌上晾干。在她离开期间，Vanya 进来了，并决定重新排列最左边的 $k$ 个指甲贴片。也就是说，选择一个排列 $p_1, \dots, p_k$，并对于每个 $1$ 到 $k$ 的 $i$，同时将从左数第 $i$ 个指甲贴片移动到第 $p_i$ 个位置。

Vanya 不希望 Polina 注意到任何异常，因此他希望桌上指甲贴片的颜色序列保持不变。Polina 非常敏锐，即使颜色顺序相同，她也可能会发现异样。所以，为了保险起见，Vanya 还希望他选择的排列中的环（cycle）的数量是 Polina 的 $m$ 个最喜欢的数字之一。

现在 Vanya 想知道，对于 $1$ 到 $n$ 之间的每个 $k$ 的选择，他可以选择多少个满足上述两个条件的不同排列。请帮他解决这个问题！由于答案可能非常大，请将它们对 $998\,244\,353$ 取模后输出。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示桌上指甲贴片的数量。

第二行包含 $n$ 个整数 $col_1, \dots, col_n$ ($1 \le col_i \le n$)，表示涂在它们上面的指甲油颜色。

第三行包含一个整数 $m$ ($1 \le m \le n$)，表示 Polina 最喜欢的数字的个数。

最后一行包含 $m$ 个互不相同的整数 $x_1, \dots, x_m$ ($1 \le x_i \le n$，$x_i \neq x_j$ 若 $i \neq j$)，表示 Polina 最喜欢的数字。

输出格式

输出一行，包含 $n$ 个整数，分别表示对于每个从 $1$ 到 $n$ 的 $k$ 的答案。

样例

输入样例 1

3
1 1 2
2
1 3

输出样例 1

1 1 1

输入样例 2

6
1 1 3 2 6 6
4
6 3 4 2

输出样例 2

0 1 2 2 1 2

输入样例 3

10
10 2 2 10 10 10 2 10 10 10
5
1 3 9 7 2

输出样例 3

1 1 2 3 7 23 53 233 1281 8454