다항식과의 게임 2

이 문제에서

• 편의상 $0^0 = 1$로 둡니다.
• $p = 998244353$으로 고정합니다. 이 수는 소수입니다.

키파는 이런 인터랙티브 문제를 내려고 했습니다.

다음과 같은 함수를 호출할 수 있습니다:

• evaluate(x): x를 다항식 $Q(x)$에 대입한 후 $p$로 나눈 나머지를 돌려줍니다.

evaluate 함수의 호출을 최대 $q$번 할 수 있습니다. 당신의 프로그램은 입력으로 $n$을 받아 $Q(x)$의 계수를 $p$로 나눈 나머지를 출력해야 합니다.

그런데, 테스트 케이스를 준비하면서 최대 $q$개의 수에 대해 차수가 $n$인 다항식을 평범하게 평가하는 것은 $O(qn)$이라는 것을 깨달았습니다! 작년처럼 편법을 쓰지 않으려고, 키파는 유능한 PSer인 캬륜하에게 어떻게든 이 문제의 빠른 인터랙터를 짜 달라고 부탁했습니다.

곤경에 처한 캬륜하는 여러분에게 도움을 청했습니다. 캬륜하 대신 인터랙터를 짜 줍시다!

첫째 줄에 $n$과 $q$가 주어집니다.

둘째 줄에 $(n+1)$개의 정수 $a_n, a_{n-1}, \ldots, a_1, a_0$이 공백을 사이에 두고 주어집니다.

셋째 줄부터 $q$개의 줄에 걸쳐 정수 $b_1, \ldots, b_q$가 주어집니다.

두 번째 줄부터 주어지는 모든 정수는 $0$ 이상 $p$ 미만입니다.

총 $q$개의 줄에 정수 하나씩을 출력합니다. $i$번째 줄에 출력하는 정수는

$\sum_{k=0}^{n} a_k b_i^k \bmod p$

여야 합니다.