Description

在 IOIC 禮品店的庫存裡，放著 $N$ 種禮物。這些禮物被分成 $K$ 類，第 $i$ 種禮物為第 $a_i$ 類，且價值為 $b_i$（為正整數）。保證同類別同價值的禮物至多只有 $998244352$ 個，且每一類別都至少有一種禮物。

參加 IOIC 的優秀學生 Wiwi 在前幾天的比賽獲得了 $M$ 張禮物兌換券，第 $j$ 張可以任選一個第 $c_j$ 類的禮物。興奮的 Wiwi 帶著他贏得的兌換券，打算找禮品店的店長 Hoho 兌換禮物。經過計算後，店長告訴她，她最多可以換到總價值不超過 $X$ 的禮物，而且還告訴她在不一定要使用所有兌換券的前提下，他有 $n_i$ 種方法可以換到價值總和為 $i$ 的禮物們。這麼多的選擇讓 Wiwi 暈頭轉向，於是她決定將這些數字抄回家再慢慢決定。

回家後，她想著想著決定同一類的禮物只想至多使用一張兌換券。而在思考要選擇哪些禮物的同時，她不小心趴在書桌上睡著了。隔天早上醒來，Wiwi 發現她竟然忘記了她有幾張兌換券，也不記得禮物有哪些，只剩眼前抄回來的數字們。
請你幫幫慌亂的 Wiwi，從紙上的資訊回推出她有哪些兌換券，並告訴她在同一類的禮物只想至多使用一張兌換券的前提下，想要換到價值總和為 $i$ 的禮物們有幾種方法？

若有多組解，請輸出 $M$ 最大的前提下，$K$ 最小的那組。

Input Format

輸入共有兩行。第一行包含一個正整數 $X$。第二行包含 $X$ 個以空白分隔的非負整數 $n_i'$，表示 $n_i$ 除以 $998244353$ 的餘數。

$X \le 5 \times 10^ 4$
$n_i' < 998244353$

Output Format

請輸出一行，包含 $X$ 個以空白分隔的非負整數，第 $i$ 個表示按照 Wiwi 的要求下，買到總價值為 $i$ 的方法數除以 $998244353$ 的餘數。

Sample Input 1

5
2 2 2 1 0

Sample Output 1

1 1 1 0 0

Sample Input 2

6
13 69 191 290 228 72

Sample Output 2

6 11 6 0 0 0

Hints

範測一中，$(a, b)_i = {(1, 1), (2, 1), (2, 2), (2, 3)}$ 且 $c_j = {1, 2}$ 是一組可行的解。
可以證明 $M$ 最大的解為 $(a, b)_i = {(1, 1), (2, 2)}$ 且 $c_j = {1, 1, 2}$。

範測二中，$M$ 最大的解為 $(a, b)_i = {(1, 1), (2, 1), (2, 1), (3, 1), (3, 1), (3, 1)}$ 且 $c_j = {1, 2, 2, 2, 3, 3}$。
此範測因此滿足子任務三的條件。

Problem Source

IOICamp 2024 Day6 pF

Subtasks

No.	Testdata Range	Constraints	Score
1	0~1	範例測資	0
2	2~11, 44~46	$X = 2$	10
3	1, 12~20	存在解滿足 $b_i = 1$，且一類玩具至多只有 $100$ 種	20
4	0~11, 21~32, 44~46	$X \le 10^ 3$	30
5	0~46	無額外限制	40

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	3000	262144	65536	1 4 5
1	3000	262144	65536	1 3 4 5
2	3000	262144	65536	2 4 5
3	3000	262144	65536	2 4 5
4	3000	262144	65536	2 4 5
5	3000	262144	65536	2 4 5
6	3000	262144	65536	2 4 5
7	3000	262144	65536	2 4 5
8	3000	262144	65536	2 4 5
9	3000	262144	65536	2 4 5
10	3000	262144	65536	2 4 5
11	3000	262144	65536	2 4 5
12	3000	262144	65536	3 5
13	3000	262144	65536	3 5
14	3000	262144	65536	3 5
15	3000	262144	65536	3 5
16	3000	262144	65536	3 5
17	3000	262144	65536	3 5
18	3000	262144	65536	3 5
19	3000	262144	65536	3 5
20	3000	262144	65536	3 5
21	3000	262144	65536	4 5
22	3000	262144	65536	4 5
23	3000	262144	65536	4 5
24	3000	262144	65536	4 5
25	3000	262144	65536	4 5
26	3000	262144	65536	4 5
27	3000	262144	65536	4 5
28	3000	262144	65536	4 5
29	3000	262144	65536	4 5
30	3000	262144	65536	4 5
31	3000	262144	65536	4 5
32	3000	262144	65536	4 5
33	3000	262144	65536	5
34	3000	262144	65536	5
35	3000	262144	65536	5
36	3000	262144	65536	5
37	3000	262144	65536	5
38	3000	262144	65536	5
39	3000	262144	65536	5
40	3000	262144	65536	5
41	3000	262144	65536	5
42	3000	262144	65536	5
43	3000	262144	65536	5
44	3000	262144	65536	2 4 5
45	3000	262144	65536	2 4 5
46	3000	262144	65536	2 4 5

Submit out of contest

53 . IOIC 禮品店