Dany jest ciąg $A_1, A_2, \ldots, A_N$ długości $N$. Napisz program, który wykonuje następujące zapytania:

• 1 i: Wypisz $A_i$. ($1 \le i \le N$)
• 2 x y t: Jeśli istnieje liczba mniejsza niż $t$ wśród $A_x, A_{x+1}, \ldots, A_y$, zignoruj to zapytanie. W przeciwnym razie odejmij $t$ od każdego z $A_x, A_{x+1}, \ldots, A_y$. ($1 \le x \le y \le N$, $1 \le t \le 10^{18}$)
• 3 x y t: Dla wszystkich $x \le i \le y$ ustaw $A_i = t + i - y$. ($1 \le x \le y \le N$, $t - y + x \ge 0$, $1 \le t \le 10^{18}$)
• 4 x y: Dla wszystkich $x \le i \le y$ ustaw $A_i = \lfloor \sqrt A_i \rfloor$. ($1 \le x \le y \le N$)

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $N$ i $Q$, długość ciągu oraz liczbę zapytań. ($1 \le N \le 100\,000$, $1 \le Q \le 500\,000$)

Drugi wiersz zawiera $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 10^{18}$)

Kolejne $Q$ wierszy zawiera po jednym zapytaniu, jak opisano powyżej.

Wyjście

Dla każdego zapytania typu 1 i wypisz w osobnym wierszu wynik w kolejności.

Przykład

Wejście 1

```

#### Wyjście 1

```