Два замість трьох
Нехай є два масиви дійсних чисел: 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 (1 ≤ A, B, C, D ≤ 1000). У другому рядку вхідних даних записано ціле число q (1 ≤ q ≤ 10^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}.