Two Instead of Three#5950
Sign in

Two Instead of Three

2 seconds
64 megabytes
Medium

Let there be two arrays of real numbers: X = (x_0, x_1, \ldots, x_{n-1}) and Y = (y_0, y_1, \ldots, y_{n-1}). Each array contains exactly 2^{30} elements (meaning n = 2^{30}). Let us denote z_k = x_k + iy_k, k = 0, 1, \ldots, 2^{30}-1. The discrete Fourier transform has already been performed for z_k and it is known that

\begin{aligned} \text{real}(z_k) &= ((A^2 k + B^2) \bmod 1000) \cdot 10^{-3}\\ \text{imag}(z_k) &= ((C^2 k + D^2) \bmod 1000) \cdot 10^{-3} \end{aligned}

Let A = \text{DFT}_n(X), B = \text{DFT}_n(Y). Your task is to determine A_k and B_k for a given index .

Input

The first line of input contains integers , , , (1 \leq A, B, C, D \leq 1000). The second line contains an integer (1 \leq q \leq 10^5). The next line contains space-separated integers — the indices for which A_k and B_k need to be calculated (each index is at least and at most 2^{30}-1).

Output

Output exactly lines. In each of the lines, output four numbers: \text{real}(A_k), \text{imag}(A_k), \text{real}(B_k), \text{imag}(B_k). Separate numbers in a line with spaces. Separate answers for different indices with line breaks. Output numbers with relative or absolute error not exceeding 10^{-6}.

Examples

Example 1

Loading
Loading