30996번 - 주사위 던지기 스페셜 저지

문제

$N$면체 주사위가 있고 $i$번째 면에는 수 $i$가 적혀 있다. $i$번째 면이 나올 확률은 $\displaystyle{\frac{A_i}{\sum_{i=1}^{N} A_i}}$ 이다. 이때 다음과 같은 쿼리에 $Q$회 답하라.

• $x$: 주사위를 $M$번 던졌을 때 나오는 눈의 합이 1ドル$ 이상 $x$ 이하일 확률을 출력하라.

입력

첫 번째 줄에는 정수 $N, M, Q$가 공백으로 구분되어 주어진다.

두 번째 줄에는 $A_1, A_2, \cdots, A_N$ 이 공백으로 구분되어 주어진다.

세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 주어진다.

입력에 주어지는 모든 수는 정수이다.

출력

$Q$개의 줄에 걸쳐 정답을 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10ドル^{-1}$ 이하이면 정답이다.

제한

• 1ドル \le N \le 100$
• 1ドル \le M, Q \le 5 \times 10^3$
• 1ドル \le A_i \le 10^3$
• 1ドル \le x \le N \times M$

힌트