Раздвоение
Обозначим две последовательности действительных чисел 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}.