The Fourier transform is a classic problem with profound significance in mathematics, engineering, and computer science. The Fast Fourier Transform (FFT), one of the top ten algorithms of the twentieth century, has improved the running time of many algorithms. For example, it allows polynomial convolution to be solved in $\Theta(n \log n)$ time, compared to the $\Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$ complexity of the Karatsuba algorithm.

We define the Fourier transform here. Let $\widehat A$ be the discrete Fourier transform of $A$:

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

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

EI is practicing how to write FFT on an OJ. However, this particular problem on the OJ is quite peculiar: the server interacts with the student's program, querying some values of the transformed array and comparing them with the results of a reference solution.

Unfortunately, this OJ is extremely unreliable and frequently malfunctions. The main reason is that sunspots change the values of the original array, causing the values after the FFT to change. The magical reference solution is able to recompute any single term of the FFT-transformed array in $\Theta(1)$ time.

EI is at a loss and would like you to help him.

Problem Summary: Maintain an array, support point updates, and query the value of a specific point in the Fourier-transformed array.

Input

The first line contains two positive integers $k$ and $q$, representing the array length $n = 2^k$ and the number of operations, respectively.

The next line contains $n$ integers representing each term $A_i$ of the array.

The following lines each start with an integer $opt$, representing the operation type, followed by 1 or 2 numbers.

$1\ i\ x$ means to add $x$ to $A_i$.

$2\ i$ means to query the value of $\widehat A_i$.

Note: The array is 0-indexed, and all inputs are integers.

Output

For each query operation, output two real numbers on a single line representing the real and imaginary parts, respectively.

The absolute difference from the standard answer should not exceed $10^{-4}$.

Examples

Input 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

Output 1

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

Constraints

$|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$, number of queries $1 \le q_{\text{query}} \le 500$

Subtask 2 (14 pts.): $1 \le k \le 14$, $1 \le q \le 5 \times 10^4$, number of updates $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$