Bifurcation
Denote two sequences of real numbers x(k) and y(k). We define a sequence of complex numbers z(k): z(k) = x(k) + iy(k).
Let FFT_N(k, z) = . Defined similarly FFT_N(k, x) and FFT_N(k, y).
Required by the calculated values FFT_N(k, z) to restore the values FFT_N(k, x) and FFT_N(k, y).
Input
The first line of the input file contains an integer N (1 ≤ N ≤ 2^30, N is a power of two). Followed by non-negative integers A, B, C, D, E, F, do not exceed 1000. To save time entering a value FFT_N(k, z) must be calculated as follows:
FFT_N(k, z).real = ((A + B·k) xor (C·k))·10^{-3}, FFT_N(k, z).imag = ((D + E·k) xor (F·k))·10^{-3},
where FFT_N(k, z).real and FFT_N(k, z).imag — real and imaginary parts, respectively.
Then, given the number of M - the number of queries (1 ≤ M ≤ 10^5). Followed by M integers q_i (0 ≤ q_i ≤ N).
Output
The output file output the M lines. In the j-th line FFT_N(q_j, x) and FFT_N(g_j, y). Values should be different from the right is not more than 10^{-4}.