Bifurcation — Eolymp

Input

The first line contains an integer $N$ ( $1 \leq N \leq 2^{30}$ 1 \leq N \leq 2^{30}, $N$ is a power of two). Then six non-negative integers $A$ , $B$ , $C$ , $D$ , $E$ , $F$ follow, each not exceeding $1000$ . For convenience, the value $FFT_{N} (k, z)$ \mathrm{FFT}_N(k, z) is calculated by the formulas:

FFT_{N} (k, z) . real = ((A + B \cdot k) xor (C \cdot k)) \cdot 1 0^{- 3}

\mathrm{FFT}_N(k, z).\mathrm{real} = ((A + B \cdot k)\ \mathrm{xor}\ (C \cdot k)) \cdot 10^{-3}

FFT_{N} (k, z) . imag = ((D + E \cdot k) xor (F \cdot k)) \cdot 1 0^{- 3}

\mathrm{FFT}_N(k, z).\mathrm{imag} = ((D + E \cdot k)\ \mathrm{xor}\ (F \cdot k)) \cdot 10^{-3}

where $FFT_{N} (k, z) . real$ \mathrm{FFT}_N(k, z).\mathrm{real} and $FFT_{N} (k, z) . imag$ \mathrm{FFT}_N(k, z).\mathrm{imag} are the real and imaginary parts, respectively.

Then $M$ ( $1 \leq M \leq 1 0^{5}$ 1 \leq M \leq 10^5), the number of queries, is given. Then $M$ integers $q_{i}$ q_i ( $0 \leq q_{i} \leq N$ 0 \leq q_i \leq N) follow.

Output

The output should contain $M$ lines. In the $j$ -th line, print the values $FFT_{N} (q_{j}, x)$ \mathrm{FFT}_N(q_j, x) and $FFT_{N} (q_{j}, y)$ \mathrm{FFT}_N(q_j, y). The output values must differ from the correct ones by no more than $1 0^{- 4}$ 10^{-4}.

Examples

Example 1

Loading