차수가 N이고 계수가 정수인 다항식 f(x) = a₀ + a₁x + a₂x² + ... + a_Nx^N이 주어진다.</p>

K개의 정수 x₁, x₂, ..., x_K가 주어졌을 때, f(x₁), f(x₂), ..., f(x_K)를 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 다항식의 차수 N(0 ≤ N ≤ 250,000)이 주어진다.</p>

둘째 줄에는 N+1개의 정수가 주어진다. i번째 정수는 다항식의 계수 a_i-1이다. (0 ≤ a_i < 786,433)

셋째 줄에는 정수의 개수 K가 주어진다. (1 ≤ K ≤ 250,000)

넷째 줄에는 x₁, x₂, ..., x_K가 주어진다. (0 ≤ x_j < 786,433)

출력 형식

총 K개의 줄을 출력한다. i번째 줄에는 f(x_i)의 값을 786433로 나눈 나머지를 출력한다.

예제 입력

2
1 2 3
3
7 8 9

예제 출력

162
209
262