GCD and Power Sum

You are given two sequences of n positive integers: \(a_1,a_2,\dots,a_n\) and \(b_1,b_2,\dots,b_n\). For each index \(i \in [1, n]\), define

\(A_i = \sum_{j=1}^{n} i^j \cdot \gcd(a_i, b_j)\)

outputting the value modulo \(998\,244\,353\). In other words, you need to compute \(n\) results where the i-th result is the sum of \(i^j \cdot \gcd(a_i,b_j)\) for all \(j=1,2,\dots,n\), reduced modulo \(998\,244\,353\). Note that all exponentiations are standard power operations.

inputFormat

The input consists of three lines:

1. An integer n representing the number of elements in each sequence.
2. n space-separated positive integers representing the array \(a\): a_1, a_2, \dots, a_n.
3. n space-separated positive integers representing the array \(b\): b_1, b_2, \dots, b_n.

outputFormat

Output n lines. The i-th line should contain the value of \(A_i\) modulo \(998\,244\,353\).

sample

1
10
20

10