Q - サイコロ 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 5 点

問題文

2 個のサイコロがあり、それぞれサイコロ 1, サイコロ 2 と呼びます。
サイコロ 1 は正整数 A_1, A_2, \dots, A_N が等確率で出る N 面サイコロです。ここで A_1, A_2, \dots, A_N は相異なります。
サイコロ 2 は正整数 B_1, B_2, \dots, B_M が等確率で出る M 面サイコロです。ここで B_1, B_2, \dots, B_M は相異なります。
正整数 K が与えられます。k=1,2,\dots,K について次の問題を解いてください。

  • サイコロ 1 とサイコロ 2 を同時に振った時の、出た整数の和の k 乗の期待値を \text{mod }998244353 で求めよ。
期待値 \text{mod }998244353 とは 求める期待値は必ず有理数となることが証明できます。 またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq 10^5
  • 1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^8
  • 1 \leq B_1 \lt B_2 \lt \dots \lt B_M \leq 10^8
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M K
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M

出力

K 行出力せよ。i 行目には k=i の時の答えを出力せよ。

入力例 1

3 2 3
1 2 3
4 5

出力例 1

499122183
166374102
499122469

例えばサイコロ 1 とサイコロ 2 を同時に振って 3 と 5 が出た場合、和の 3 乗は (3+5)^3=512 になります。

入力例 2

8 9 5
26056440 37770730 49119845 54471601 59187620 86450214 95205990 97771081
12521133 14054302 19786177 21524935 39265456 53591023 65158870 86176948 87221915

出力例 2

981084750
45312313
562611236
522662310
196292405

Score: 5 points

Problem Statement

There are two dice, called die 1 and die 2.

  • Die 1 is an N-sided die, where each side shows a distinct positive integer A_1, A_2, \dots, A_N with equal probability.
  • Die 2 is an M-sided die, where each side shows a distinct positive integer B_1, B_2, \dots, B_M with equal probability.

You are also given a positive integer K.
For each k = 1, 2, \dots, K, solve the following problem:

  • When rolling die 1 and die 2 simultaneously, compute the expected value of (\text{sum of the outcomes})^k modulo 998244353.
What does expected value modulo 998244353 mean? It can be proven that the expected value is always a rational number. Under the constraints of this problem, if the value can be expressed as \tfrac{P}{Q} with coprime integers P and Q, then there exists a unique integer R such that R \times Q \equiv P \pmod{998244353} and 0 \leq R < 998244353. You are asked to compute this R.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq 10^5
  • 1 \leq A_1 < A_2 < \dots < A_N \leq 10^8
  • 1 \leq B_1 < B_2 < \dots < B_M \leq 10^8
  • All input values are integers

Input

The input is given from standard input in the following format:

N M K
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M

Output

Print K lines. On the i-th line, output the answer for k = i.

Sample Input 1

3 2 3
1 2 3
4 5

Sample Output 1

499122183
166374102
499122469

For example, if die 1 shows 3 and die 2 shows 5, then the cube of the sum is (3+5)^3 = 512.

Sample Input 2

8 9 5
26056440 37770730 49119845 54471601 59187620 86450214 95205990 97771081
12521133 14054302 19786177 21524935 39265456 53591023 65158870 86176948 87221915

Sample Output 2

981084750
45312313
562611236
522662310
196292405