Description

Given $n$ positive integers $a_1,a_2,\dots,a_n$, and another $n$ positive integers $b_1,b_2,\dots,b_n$, you need to compute the greatest common divisor of $a_i$ and $b_j$ for every pair $(i,j)$.

It is not hard to see that the output should contain $n^2$ positive integers. To reduce the impact of output on the program’s running efficiency, you only need to output $n$ lines, with one integer $A_i$ per line.

For $i\in[1,n]$, $A_i=\sum_{j=1}^{n}i^j\gcd(a_i,b_j)$. Since the answer may be too large, you only need to output the result modulo $998,244,353$.

Input Format

The first line contains one positive integer $n$.

The second line contains $n$ positive integers, representing $a_1,a_2,\dots,a_n$.

The third line contains $n$ positive integers, representing $b_1,b_2,\dots,b_n$.

Output Format

Output $n$ lines. The $i$-th line should contain one non-negative integer $A_i$. Its meaning is described in the statement.

5
200 300 300 300 23333
666 666 666 666 123456

16
564
3636
14328
3905

Hint

For $20\%$ of the testdata, $1\leqslant n\leqslant 500$.

For $100\%$ of the testdata, $1\leqslant n\leqslant 5000;1\leqslant a_i,b_i\leqslant 10^6$.

Please pay attention to the impact of constant factors on the program’s running efficiency.

Translated by ChatGPT 5