Преобразование Фурье — это классическая задача, имеющая глубокое значение в математике, инженерии и информатике. Быстрое преобразование Фурье (Fast Fourier Transform, FFT), входящее в десятку важнейших алгоритмов двадцатого века, позволило значительно улучшить время работы многих алгоритмов. Например, оно позволило свести задачу умножения многочленов с $\Theta\left( n ^ {\log_2 3}\right) \approx \Theta(n^{1.585})$ (алгоритм Карацубы) к $\Theta(n\log n)$ при использовании FFT.

Определим преобразование Фурье: пусть $\widehat A$ — дискретное преобразование Фурье последовательности $A$:

$$ \widehat A_i = \sum_{j = 0}^{n - 1} \omega_n^{ij} A_j $$

где $\omega_n^{k} = \mathrm{e}^{2\pi \mathrm{i}k/n}$.

EI тренируется решать задачи на FFT в системе онлайн-проверки (OJ), однако эта задача в OJ довольно необычна: сервер взаимодействует с программой студента, запрашивая значения некоторых элементов преобразованного массива и сравнивая их с результатами эталонного решения.

К несчастью, этот OJ работает крайне нестабильно, в основном из-за того, что солнечные вспышки изменяют значения исходного массива, из-за чего значения после FFT также меняются. Удивительно, но эталонное решение способно каждый раз пересчитывать конкретный элемент массива после FFT за время $\Theta(1)$.

EI задумался, что делать, и просит вас помочь ему.

Краткое условие: поддерживайте массив, выполняя операции изменения элемента и запроса значения элемента в массиве после преобразования Фурье.

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

В первой строке заданы два целых положительных числа $k$ и $q$, где $n = 2^k$ — длина массива, а $q$ — количество операций.

В следующей строке заданы $n$ чисел — элементы массива $A_i$.

Далее следуют $q$ строк, в каждой из которых первое число $opt$ обозначает тип операции, за которым следуют 1 или 2 числа.

$1\ i\ x$ означает прибавление $x$ к $A_i$.

$2\ i$ означает запрос значения $\widehat A_i$.

Примечание: индексация массива начинается с 0, все входные данные — целые числа.

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

Для каждого запроса выведите в отдельной строке два вещественных числа: действительную и мнимую части результата.

Абсолютная погрешность по сравнению со стандартным ответом не должна превышать $10^{-4}$.

Примеры

Пример 1

2 9
1 3 2 -2
2 0
2 1
2 2
2 3
1 2 -1
2 0
2 1
2 2
2 3

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

4 0
-1 5
2 0
-1 -5
3 0
0 5
1 0
0 -5

Ограничения

$|A_i|, |x| \le 10$, $1 \le k \le 18$, $1 \le q \le 10^5$, $0 \le i < n$

Подзадача 1 (8 баллов): $1 \le k \le 14$, $1 \le q \le 5 \times 10^4$, количество запросов $1 \le q_{\text{query}} \le 500$

Подзадача 2 (14 баллов): $1 \le k \le 14$, $1 \le q \le 5 \times 10^4$, количество модификаций $1 \le q_{\text{change}} \le 500$

Подзадача 3 (34 балла): $1 \le k \le 16$, $1 \le q \le 5 \times 10^4$

Подзадача 4 (44 балла): $1 \le k \le 18$, $1 \le q \le 10^5$