디리클레 합성곱과 누적합

테스트 케이스가 $T$개 있다.

양의 정수 $N$이 주어질 때, $Q_N=\lbrace {\lfloor {N \over x} \rfloor \colon x \in \mathbb{Z}, 1 \leq x \leq N} \rbrace$을 정의한다.

$Q_N$의 원소를 오름차순으로 배열한 수열을 $(a_0,a_1,\ldots,a_{k-1})$로 나타낸다.

수열 $f, g \colon \mathbb{N} \to \mathbb{Z}$에 대해, 각 $x \in Q_N$까지의 누적합을 다음과 같이 정의한다.

이들이 주어질 때, 다음과 같이 정의되는 디리클레 합성곱 $h=f * g$에 대해 각 $x \in Q_N$까지의 누적합을 계산한다.

제한 조건

• $1 \leq N \leq 1000000000000$
• $1 \leq f_x,g_x < 998244353$
• $T>1$이면, $T=10000$이고 각 $N=1,2,\ldots,10000$마다 테스트 케이스가 정확히 하나 존재한다.

$T$
$case_1$
$\vdots$
$case_T$

각 테스트 케이스는 다음 형식으로 주어진다.

$N$
$f_{a_0}$ $f_{a_1}$ $\ldots$ $f_{a_{k-1}}$
$g_{a_0}$ $g_{a_1}$ $\ldots$ $g_{a_{k-1}}$

$h_{a_0}$ $h_{a_1}$ $\ldots$ $h_{a_{k-1}}$