傅里叶变换是一个经典的问题，它在数学、工程、计算机科学中都有着深刻的意义。而二十世纪十大算法之一的快速傅里叶变换 (Fast Fourier Transform, FFT) 使它改善了许多算法的运行时间，例如将多项式卷积从 $\Theta\left( n ^ {\log_2 3}\right) \approx \Theta(n^{1.585})$ 的 Karatsuba 算法变成了套用 FFT 即可 $\Theta(n\log n)$ 即可解决的问题。

在此明确傅里叶变换的定义，记 $\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 在 OJ 上刷题练习如何写 FFT ，然而这个 OJ 的这道题比较神奇，服务器会与学生的程序进行交互，查询变换后的一部分取值，并且与标程的运行结果进行比对。

不妙的是此 OJ 时运极差，常常出锅，主要原因是太阳黑子会改变原数组的值，这样一来 FFT 后的值就会有变化，神奇的标程又能每次在 $\Theta(1)$ 的时间内重新算出 FFT 后数组的某一项。

EI 想了想，他并不知道该怎么办，他希望你来帮助一下他。

一句话题意：维护一个数组，支持单点修改，对傅里叶变换后的数组单点查值。

输入格式

第一行，输入两个正整数 $k, q$ 表示数组长度 $n = 2^k$ 和操作次数。

接下来一行 $n$ 个数表示数组的每一项 $A_i$。

接下来行，每行第一个数 $opt$ 表示操作类型，后面跟有 1 或 2 个数。

$1\ i\ x$ 表示 $A_i$ 加上 $x$。

$2\ i$ 表示查询 $\widehat A_i$ 的值。

注意：数组是从 0 开始计数的，输入的都是整数。

输出格式

对于每个询问操作，一行输出两个实数分别表示实部和虚部。

与标准答案差的绝对值不应超过 $10^{-4}$ 即可。

样例 1

input

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

output

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$

Subtask 1 (8 pts.)，$1 \le k \le 14$, $1 \le q \le 5 \times 10^4$，查询次数 $1 \le q_{\text{query}} \le 500$

Subtask 2 (14 pts.)，$1 \le k \le 14$, $1 \le q \le 5 \times 10^4$，修改次数 $1 \le q_{\text{change}} \le 500$

Subtask 3 (34 pts.)，$1 \le k \le 16$, $1 \le q \le 5 \times 10^4$

Subtask 4 (44 pts.)，$1 \le k \le 18$, $1 \le q \le 10^5$

时间限制：$2\,\mathrm{s}$

空间限制：$256\,\mathrm{MB}$