Polynomial and Queries

You are given a polynomial $f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_N x^N$ of degree $N$ with integer coefficients.

Given the integers $x_1, x_2, \ldots, x_K$, write a program that computes $f(x_j)$ modulo 786433 for every $j$.

The first line contains the degree $N$ of the polynomial. ($0 \le N \le 250000$)

The second line contains $N+1$ integers. The $i$-th integer is the coefficient $a_{i-1}$. ($0 \le a_i < 786433$)

The third line contains the number of integers $K$. ($1 \le K \le 250000$)

The fourth line contains $x_1, x_2, \ldots, x_K$. ($0 \le x_j < 786433$)

Print $K$ lines. The $i$-th line contains $f(x_i)$ modulo 786433.