Transformata Fouriera to klasyczny problem, który ma głębokie znaczenie w matematyce, inżynierii i informatyce. Szybka transformata Fouriera (Fast Fourier Transform, FFT), uznawana za jeden z dziesięciu najważniejszych algorytmów XX wieku, pozwoliła znacząco poprawić czasy działania wielu algorytmów. Przykładowo, dzięki niej złożoność obliczeniowa splotu wielomianów została zredukowana z $\Theta\left( n ^ {\log_2 3}\right) \approx \Theta(n^{1.585})$ (algorytm Karatsuby) do $\Theta(n\log n)$ przy użyciu FFT.

Poniżej definiujemy transformatę Fouriera. Niech $\widehat A$ będzie dyskretną transformatą Fouriera ciągu $A$:

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

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

EI ćwiczy na platformie OJ implementację FFT. Jednakże zadanie na tej platformie jest dość nietypowe: serwer wchodzi w interakcję z programem użytkownika, odpytując o wybrane wartości po transformacie i porównując je z wynikami wzorcowymi.

Niestety, platforma ta działa bardzo niestabilnie, głównie z powodu plam na Słońcu, które zmieniają wartości w oryginalnej tablicy, co z kolei wpływa na wyniki FFT. Magiczny wzorzec potrafi za każdym razem przeliczyć wybrany element tablicy po FFT w czasie $\Theta(1)$.

EI zastanawia się, co z tym zrobić i prosi Cię o pomoc.

Skrócona treść zadania: Utrzymuj tablicę, obsługując modyfikacje pojedynczych elementów oraz zapytania o wartości pojedynczych elementów po transformacie Fouriera.

Wejście

W pierwszej linii podano dwie dodatnie liczby całkowite $k, q$, oznaczające długość tablicy $n = 2^k$ oraz liczbę operacji.

W kolejnej linii znajduje się $n$ liczb oznaczających poszczególne elementy tablicy $A_i$.

Następnie podano $q$ linii, z których każda zaczyna się od liczby $opt$ określającej typ operacji, po której następują 1 lub 2 liczby.

$1\ i\ x$ oznacza dodanie $x$ do $A_i$.

$2\ i$ oznacza zapytanie o wartość $\widehat A_i$.

Uwaga: Indeksowanie tablicy zaczyna się od 0, wszystkie dane wejściowe są liczbami całkowitymi.

Wyjście

Dla każdego zapytania wypisz w jednej linii dwie liczby rzeczywiste oznaczające odpowiednio część rzeczywistą i urojoną wyniku.

Wartości powinny być poprawne z dokładnością do $10^{-4}$ względem odpowiedzi wzorcowej.

Przykład

Wejście 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

Wyjście 1

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

Ograniczenia

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

Podzadanie 1 (8 pkt.): $1 \le k \le 14$, $1 \le q \le 5 \times 10^4$, liczba zapytań $1 \le q_{\text{query}} \le 500$

Podzadanie 2 (14 pkt.): $1 \le k \le 14$, $1 \le q \le 5 \times 10^4$, liczba modyfikacji $1 \le q_{\text{change}} \le 500$

Podzadanie 3 (34 pkt.): $1 \le k \le 16$, $1 \le q \le 5 \times 10^4$

Podzadanie 4 (44 pkt.): $1 \le k \le 18$, $1 \le q \le 10^5$