eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Роздвоєння

Роздвоєння

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

Позначимо дві послідовності дійсних чисел 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 (1N2^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 — кількість запитів (1M10^5). Далі йде M цілих чисел q_i (0q_iN).

Вихідні дані

У вихідний файл виведіть M рядків. У j-ому рядку — значення FFT_N(q_j, x) і FFT_N(g_j, y). Значення повинні відрізнятись від вірних не більше, ніж на 10^{-4}.

Приклад

Вхідні дані #1
2
1000 0 0 0 0 0
2
0 1
Вихідні дані #1
1.0000 0.0000 0.0000 0.0000
1.0000 0.0000 0.0000 0.0000
Автор Дмитро Жуков
Джерело Зимова Школа, Харків 2011, День 2