基于值域预处理的快速 GCD

题目背景

模板题,无背景。

题目描述

给定 $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$。意义见题目描述。

输入输出样例

输入样例 #1

5
200 300 300 300 23333
666 666 666 666 123456

输出样例 #1

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$。 **请注意常数因子对程序运行效率的影响**