Description

Alice and Bob are playing a game again.

In one game, first Alice receives a sequence $a$ of length $n$, and Bob receives a sequence $b$ of length $m$. Then they each randomly pick one number from their own sequence, denoted $a_x, b_y$. The $k$-th value of this game is defined as $(a_x + b_y)^k$.

Because they find this game too boring, they ask you to compute, for $i = 1, 2, \cdots, t$, the expected $i$-th value of a game.

Since the answer can be large, you only need to output the result modulo $998244353$.

Input Format

The first line contains two integers $n, m(1 \leq n, m \leq 10^5)$, representing the lengths of Alice’s and Bob’s sequences.

The next line contains $n$ numbers, where the $i$-th number is $a_i(0 \leq a_i < 998244353)$, representing Alice’s sequence.

The next line contains $m$ numbers, where the $j$-th number is $b_j(0 \leq b_j < 998244353)$, representing Bob’s sequence.

The next line contains one integer $t(1 \leq t \leq 10^5)$, as described above.

Output Format

Output $t$ lines, where the $i$-th line is the expected $i$-th value of a single game.

1 1
1
2
3

3
9
27

2 8
764074134 743107904
663532060 183287581 749169979 7678045 393887277 27071620 13482818 125504606
6

774481679
588343913
758339354
233707576
36464684
461784746

Hint

Translated by ChatGPT 5