Problem description

1. Pewnego jesiennego dnia Frymbulin miał ochotę na zupę grzybową. W związku z tym, że zupę grzybową gotuje się głównie z grzybów, wziął koszyczek i poszedł w głąb okolicznych lasów na grzyby.
2. Podczas zbierania grzybów w lesie, Frymbulin potknął się, upadł i czubkiem nosa wbił się w mech. Kiedy w końcu udało mu się wydostać nos z niewoli, zobaczył, że pod nim znajduje się ruda żelaza.

Frymbulin przypomniał sobie wtedy o swoim zamiłowaniu do rozważań ciekawych operacji na ciągach. Niestety, jest jeszcze częściowo oszołomiony po wyjściu z opresji, w której się znalazł, dlatego tym razem rozważane przez niego operacje są nieco bezsensowne.

Dany jest ciąg długości N, składający się z elementów ponumerowanych od 1 do N.

Na ciągu zostanie wykonanych Q operacji, z których każda będzie jednego z dwóch typów:

• 1 i r – operacja oznaczająca, że element na pozycji i zmienia swoją wartość na r.
• 2 l k – zapytanie o wynik poniższego procesu na przedziale naszego ciągu długości 2^k, zaczynającym się od pozycji l i kończącym się na pozycji l + 2^k − 1:
  • Proces będzie przebiegać w k krokach. Każdy krok zmniejsza długość ciągu o połowę. W danym kroku wartości są łączone w pary kolejnych (pierwsza i druga, trzecia i czwarta itd.), a następnie każda para jest zastępowana jedną wartością równą wartości bezwzględnej różnicy między nimi. Dokładniej, jeśli w jednej parze będą wartości A i B, to nowa wartość wyniesie |A−B|. Zauważ, że po k takich krokach pozostanie dokładnie jeden element. Wynikiem jest jego wartość.

Operacja typu 2 nie zmienia ciągu – wszystkie kroki wykonywane są tylko abstrakcyjnie. Należy wypisać wynik dla każdej operacji typu 2.

Wejście

W pierwszym wierszu znajdują się dwie liczby całkowite N i Q.

W następnym wierszu znajduje się N liczb całkowitych p_i oznaczających elementy ciągu.

W kolejnych Q wierszach znajdują się opisy zapytań zgodnie z treścią zadania.

Wyjście

Dla każdego zapytania typu 2 należy wypisać końcową wartość po wszystkich k krokach.

Ograniczenia

2 ≤ N ≤ 200 000, 1 ≤ Q ≤ 200 000, 0 ≤ p_i ≤ 10⁹.

Dla zapytań typu 1 zachodzi 1 ≤ i ≤ N, 0 ≤ r ≤ 10⁹.

Dla zapytań typu 2 zachodzi 1 ≤ l ≤ N, 1 ≤ l + 2^k − 1 ≤ N.

Podzadania

Testy przykładowe

5 3
4 8 2 0 7
2 1 2
1 1 9
2 2 1

2
6

8 6
1 2 3 4 5 6 7 8
2 1 3
1 4 1
1 7 3
2 1 3
1 2 100
2 2 2

0
3
93

9 5
1 0 2 0 4 1 3 2 8
2 2 3
2 1 3
1 5 1
1 6 4
2 4 2

2
1
0

Wyjaśnienie

W pierwszym zapytaniu pierwszego testu wartości będą się zmieniać następująco: (4,8,2,0) → (4,2) → (2)

W trzecim zapytaniu pierwszego testu wartości będą się zmieniać następująco:
(8,2) → (6)