Expected k-th Value Game

Alice and Bob are playing a game. In one game, Alice receives a sequence \(a\) of length \(n\) and Bob receives a sequence \(b\) of length \(m\). Then, each of them randomly picks one number from their own sequence: let the numbers be \(a_x\) and \(b_y\) respectively. The k-th value of this game is defined as \((a_x+b_y)^k\).

Your task is to help them compute, for every \(k=1,2,\dots,t\), the expected value of a game, i.e. the expectation of \((a_x+b_y)^k\). Since the answer might be huge, output it modulo \(998244353\).

The expectation is taken over the uniform random choice of an element from each sequence. More formally, the answer for a given \(k\) is

[ E_k = \frac{1}{nm}\sum_{x=1}^{n}\sum_{y=1}^{m}(a_x+b_y)^k \pmod{998244353}. ]

inputFormat

The first line contains three integers \(n\), \(m\) and \(t\) \( (1 \leq n,m \leq 10^5, 1 \le t \le 1000)\), representing the lengths of sequences and the maximum exponent to be queried.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) \(\; (0 \le a_i < 998244353)\).

The third line contains \(m\) integers \(b_1, b_2, \dots, b_m\) \(\; (0 \le b_i < 998244353)\).

outputFormat

Output \(t\) lines. The \(k\)-th line (for \(k=1,2,\dots,t\)) should contain a single integer: the expected value for exponent \(k\) modulo \(998244353\).

sample

2 2 2
1 2
3 4

5
499122202