Роздвоєння
Позначимо дві послідовності дійсних чисел x(k) та y(k). Визначимо послідовність комплексних чисел z(k): z(k) = x(k) + iy(k).
Нехай FFT_N(k, z) = . Аналогічним чином визначаються FFT_N(k, x) і FFT_N(k, y).
Потрібно за обчисленими значеннями FFT_N(k, z) відновити значення FFT_N(k, x) и FFT_N(k, y).
Вхідні дані
У першому рядку вхідного файлу записано ціле число N (1 ≤ N ≤ 2^30, N є степінню двійки). Далі йдуть цілі невід'ємні числа A, B, C, D, E, F, які не перевищують 1000. Для экономії часу введення значення FFT_N(k, z) потрібно буде обчислювати за наступними формулами:
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},
де FFT_N(k, z).real і FFT_N(k, z).imag — дійсна та уявна частини відповідно.
Потім задано число M — кількість запитів (1 ≤ M ≤ 10^5). Далі йде M цілих чисел q_i (0 ≤ q_i ≤ N).
Вихідні дані
У вихідний файл виведіть M рядків. У j-ому рядку — значення FFT_N(q_j, x) і FFT_N(g_j, y). Значення повинні відрізнятись від вірних не більше, ніж на 10^{-4}.