최대공약수 합성곱

정수 수열 $a_1, ..., a_{N}$와 $b_1, ..., b_{N}$가 주어진다. 다음과 같이 정수 수열 $c_1, ..., c_{N}$를 계산한다:

$c_k = \sum_{\gcd(i,j)=k} a_ib_j \bmod 998244353$

제약 조건

• $1 \leq N \leq 1000000$
• $0 \leq a_i, b_i < 998244353$

$N$
$a_1$ ... $a_{N}$
$b_1$ ... $b_{N}$

$c_1$ ... $c_{N}$