フーリエ変換は数学、工学、計算機科学において深い意義を持つ古典的な問題です。20世紀の10大アルゴリズムの一つである高速フーリエ変換（Fast Fourier Transform, FFT）は、多くのアルゴリズムの実行時間を改善しました。例えば、多項式畳み込みにおいて、Karatsuba法による $\Theta\left( n ^ {\log_2 3}\right) \approx \Theta(n^{1.585})$ の計算量を、FFTを用いることで $\Theta(n\log n)$ で解決できるようになりました。

ここでフーリエ変換の定義を明確にします。$A$ の離散フーリエ変換を $\widehat 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はどうすればよいか分からず、あなたに助けを求めています。

問題の要約：配列を管理し、単点更新およびフーリエ変換後の配列の単点値取得をサポートせよ。

入力

1行目に、配列の長さ $n = 2^k$ を表す正整数 $k$ と、操作回数を表す $q$ が与えられます。

続く1行に、配列の各要素 $A_i$ が与えられます。

続く $q$ 行には、各操作が与えられます。各行の最初の数値 $opt$ は操作の種類を表し、その後に1つまたは2つの数値が続きます。

$1\ i\ x$ は $A_i$ に $x$ を加算することを表します。

$2\ i$ は $\widehat A_i$ の値を問い合わせることを表します。

注意：配列は0からインデックス付けされ、入力はすべて整数です。

出力

各問い合わせ操作に対し、実部と虚部をそれぞれ1行に空白区切りで出力してください。

標準解との絶対誤差が $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

制限と制約

• 時間制限: 2.0秒
• メモリ制限: 256MB

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