Два вместо трёх
Пусть есть два массива действительных чисел: 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.
Input
В первой строке входных данных записаны целые числа A, B, C, D (1 ≤ A, B, C, D ≤ 1000). Во второй строке входных данных записано целое число q (1 ≤ q ≤ 10^5). В следующей строке записано q целых чисел через пробел — индексы, для которых нужно посчитать A_k и B_k (каждый из индексов не менее 0 и не более 2^30-1).
Output
Выведите ровно q строк. В каждой из q строк выводите четыре числа: real(A_k), imag(A_k), real(B_k), imag(B_k). Числа в строке разделяйте пробелами. Ответы для различных индексов k разделяйте переводами строк. Выводите числа с относительной или абсолютной погрешностью не более 10^{-6}.