Problem description

Wchodzisz do ogromnego i rozległego lasu przedziałowego, wiesz, że to dopiero Twoje pierwsze zmagania z wręcz nieprzeliczalną ilością rozmaitych wariantów drzew przedziałowych. Wchodzisz pewnie, choć zdajesz sobie sprawę z tego, że zgubisz się w nim wiele razy. Pociesza cię fakt, tego, że z każdym odnalezieniem się w lesie przedziałowym będziesz stawał się silniejszy, będziesz mógł wchodzić coraz głębiej. Jeśli będziesz wytrwały dotrzesz nawet do najciemniejszych zakamarków lasu przedziałowego – wzgórza treap-ów czy przełęczy dynamicznie rozwijanych drzew. No ale wracając do teraźniejszości, teraz jesteś dość płytko, nie widziałeś jeszcze nigdy tańczących drzew czy innych przerażających struktur drzewiastych. Twój dzisiejszy przeciwnik drzewo typu przedział punkt nie jest zbyt trudnym przeciwnikiem dla ludzi wprawionych w zgłębianiu tajemnic lasu przedziałowego, jednak dla Ciebie jako początkującego powinien sprawić jakieś wyzwanie.

Drzewo typu przedział–punkt powinno udostępniać dwie operacje – dodania wartości na przedziale i podania wartości w punkcie, musisz zatem napisać program, który wykona Q operacji dwóch typów:

• query X – podanie wartości w punkcie X.
• update X Y Z – dodanie wartości Z do wszystkich punktów z przedziału od X do Y.

Wejście

W pierwszym wierszu wejścia znajduje się dwie liczby naturalne N i Q, oddzielone pojedynczym odstępem i oznaczające odpowiednio maksymalny zakres operacji na drzewie i liczbę operacji do wykonania. W drugim wierszu wiersza znajduje się N liczb naturalnych A_i, pooddzielanych pojedynczymi odstępami i oznaczających początkowe wartości kolejnych punktów. W kolejnych Q wierszach znajdują się opisy operacji zgodne z powyższym schematem.

Wyjście

Dla każdej operacji pierwszego typu na standardowe wyjście należy wypisać jedną liczbę całkowitą – wartość w danym punkcie.

Ograniczenia

1 ≤ N ≤ 1 000 000, 1 ≤ Q ≤ 500 000, 1 ≤ X ≤ Y ≤ N, 0 ≤ A_i, Z ≤ 10⁹.

Przykład

5 5
1 4 3 2 3
query 3
update 1 4 2
update 3 5 1
query 3
query 2

3
6
6