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

Два вместо трёх

Два вместо трёх

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Пусть есть два массива действительных чисел: X = (x_0, x_1, ..., x_{n-1}) и Y = (y_0, y_1, ..., y_{n-1}). Каждый массив содержит ровно 2^30 элементов (значит n = 2^30). Обозначим z_{k }= x_{k }+ iy_k, k = 0, 1, ..., 2^30-1. Для z_k уже проведено дискретное преобразование Фурье и известно, что

Пусть A = DFT_n(X), B = DFT_n(Y). Ваша задача — определять A_k и B_k по заданному индексу k.

Входные данные

В первой строке входных данных записаны целые числа A, B, C, D (1A, B, C, D1000). Во второй строке входных данных записано целое число q (1q10^5). В следующей строке записано q целых чисел через пробел — индексы, для которых нужно посчитать A_k и B_k (каждый из индексов не менее 0 и не более 2^30-1).

Выходные данные

Выведите ровно q строк. В каждой из q строк выводите четыре числа: real(A_k), imag(A_k), real(B_k), imag(B_k). Числа в строке разделяйте пробелами. Ответы для различных индексов k разделяйте переводами строк. Выводите числа с относительной или абсолютной погрешностью не более 10^{-6}.

Пример

Входные данные #1
5 4 30 20
5
0 1 17 1000000000 7
Выходные данные #1
0.0160000000 0.0000000000 0.4000000000 0.0000000000
0.3160000000 0.1000000000 0.2000000000 0.2750000000
0.3160000000 0.0000000000 0.7000000000 -0.1250000000
0.3160000000 0.2000000000 0.2000000000 0.3000000000
0.3160000000 0.0000000000 0.7000000000 0.1250000000
Автор Евгений Соболев
Источник III Международная Летняя школа программирования 2013 г. Севастополь