题目背景

模板题，无背景。

题目描述

给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$，再给定 $n$ 个正整数$b_1,b_2,\dots,b_n$，你需要对每对 $(i,j)$ 求出 $a_i$ 与 $b_j$ 的最大公因数。

不难发现你的输出应有 $n^2$ 个正整数。为了减少输出对程序的运行效率的影响，你只需要输出 $n$ 行，每行一个整数 $A_i$。

其中对于 $i\in[1,n]$，$A_i=\sum_{j=1}^{n}i^j\gcd(a_i,b_j)$。由于答案可能过大，你只需要输出模 $998,244,353$ 后的结果即可。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数，表示 $a_1,a_2,\dots,a_n$。

第三行 $n$ 个正整数，表示 $b_1,b_2,\dots,b_n$。

输出格式

共 $n$ 行，第 $i$ 行应输出一个非负整数 $A_i$。意义见题目描述。

5
200 300 300 300 23333
666 666 666 666 123456

16
564
3636
14328
3905

提示

对于 $20\%$ 的数据，$1\leqslant n\leqslant 500$。

对于 $100\%$ 的数据，$1\leqslant n\leqslant 5000;1\leqslant a_i,b_i\leqslant 10^6$。

请注意常数因子对程序运行效率的影响