傅立葉變換是一個經典的問題，它在數學、工程、計算機科學中都有著深刻的意義。而二十世紀十大算法之一的快速傅立葉變換 (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$。

接下來 $q$ 行，每行第一個數 $opt$ 表示操作類型，後面跟有 1 或 2 個數。

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

$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$

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$