#116 simple

Statement

바구니 안에 $n$ 개의 공이 있다. 각 공은 $1$ 부터 $c$ 까지의 색 중 하나를 가지고 있다. $i$ 번째 공의 색을 $a_i$ 라 하자.

다음과 같은 시행을 $m$ 회 진행한다.

각 시행에서 바구니 안의 모든 공은 같은 확률로 뽑힌다.

모든 시행이 끝난 후, 바구니에서 공 하나를 무작위로 뽑는다. 앞선 $m$ 번의 시행에서 이루어진 모든 무작위 선택과 마지막 공을 뽑는 무작위 선택을 모두 고려했을 때, 마지막으로 뽑은 공의 색이 $i$ 일 확률을 $p_i$ 라 하자.

모든 $i \in \{1, 2, \dots, c\}$ 에 대해 $p_i$ 를 구하여라.

첫 줄에는 처음 바구니에 들어 있는 공의 수 $n$ , 색의 가짓수 $c$ , 시행의 횟수 $m$ 이 공백으로 구분되어 주어진다.

둘째 줄에는 $n$ 개의 정수 $a_1, a_2, \dots, a_n$ 이 공백으로 구분되어 주어진다. $a_i$ 는 $i$ 번째 공의 색을 나타낸다.

셋째 줄에는 $m$ 개의 정수 $b_1, b_2, \dots, b_m$ 이 공백으로 구분되어 주어진다. $b_j$ 는 $j$ 번째 시행에서 추가하는 새 공의 수를 나타낸다.

$p_1, p_2, \dots, p_c$ 를 $998\,244\,353$ 으로 나눈 나머지를 공백으로 구분하여 출력한다.

구체적으로, $p_i$ 가 항상 유리수임을 보일 수 있다. $p_i$ 를 기약분수로 나타낸 것이 $\frac{x_i}{y_i}$ 일 때, 다음 조건을 만족하는 정수 $z_i$ 를 출력하면 된다. 이러한 정수 $z_i$ 가 유일하게 존재함을 증명할 수 있다.

0 \le z_i < 998\,244\,353,\qquad y_i z_i \equiv x_i \pmod{998\,244\,353}.

#	Score	Constraints
1	100	-

Sample 1

Input

5 3
3 5
2 1000000000

Output

332748118 0 332748118 0 332748118

첫 번째 예시에서 색 $2$ 와 색 $4$ 인 공은 처음부터 없으므로 이후에도 추가되지 않고, 해당 색상의 확률은 $0$ 이다.

Sample 2

Input

4 2 1
1 2 1 1
1

Output

249561089 748683265

두 번째 예시의 첫 시행에서는 뽑은 공을 제거한 뒤 같은 색의 공 하나를 넣으므로, 어떤 공이 뽑히더라도 색별 공의 개수는 변하지 않는다. 따라서 마지막에 색 $1$ 과 색 $2$ 가 뽑힐 확률은 각각 $\frac{3}{4}$ 과 $\frac{1}{4}$ 이다.