题目描述
给出两个长度为 $n$ 的序列 $a,b$（下标均从 $1$ 开始）。
对每个 $k\in [1,3n]$，求
$$c_k=\sum_{i+j+\gcd(i,j)=k} a_ib_j$$
对 $998244353$ 取模。
输入格式
第一行是一个整数 $n$。
第二行是 $n$ 个整数 $a_1\sim a_n$。
第三行是 $n$ 个整数 $b_1\sim b_n$。
输出格式
一行 $3n$ 个整数，以空格隔开，表示 $c_1\sim c_{3n}$。
样例
样例输入 1
5 1 2 3 4 5 4 3 2 1 5
样例输出 1
0 0 4 11 14 36 25 50 31 25 0 4 0 0 25
样例输入 2
20 652771664 15645959 899989170 953006689 543144961 653050220 130612728 922344293 655010654 1136110 624620683 830047923 937366569 427553358 815385912 811489896 804489812 830404385 390431291 747331506 654156578 109282046 591385 131376571 60621772 590037928 971458102 712166360 267899654 780959882 118720175 783674089 715539901 914700022 777279589 17861569 296428641 866923488 192395515 550414874
样例输出 2
0 0 826797093 988258223 630593960 860489448 682602860 928237922 731430664 207809710 548993371 360931410 78957761 655652921 580651177 510687876 267720167 792021148 143277672 971616705 35547701 70386276 135953300 565944742 178718974 534034642 878647983 879088553 379458354 580353442 488892416 9298242 27843999 690119353 912547579 63897644 245999122 961162822 128615151 847420962 0 333666295 0 0 415331022 0 0 719000002 0 0 857342243 0 0 855882811 0 0 582082845 0 0 828394490
数据范围
本题捆绑测试。
对于所有数据，$1\le n\le 2\times 10^5$，$0\le a_i,b_i<998244353$。
详细数据范围如下表：
| Subtask 编号 | $n$ | $a_i,b_i$ | 分数 |
|---|---|---|---|
| $1$ | $\le 2000$ | $\le 998244352$ | $15$ |
| $2$ | $\le 2\times 10^5$ | $=1$ | $10$ |
| $3$ | $\le 4\times 10^4$ | $\le 1$ | $10$ |
| $4$ | $\le 2\times 10^5$ | $\le 1$ | $15$ |
| $5$ | $\le 4\times 10^4$ | $\le 998244352$ | $15$ |
| $6$ | $\le 2\times 10^5$ | $\le 998244352$ | $35$ |