Дана последовательность $A_1, A_2, \ldots, A_N$ длины $N$. Напишите программу, которая выполняет следующие запросы:
1 i: Вывести $A_i$. ($1 \le i \le N$)2 x y t: Если среди $A_x, A_{x+1}, \ldots, A_y$ существует число, меньшее $t$, то игнорировать этот запрос. В противном случае вычесть $t$ из каждого $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: Для всех $x \le i \le y$ установить $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: Для всех $x \le i \le y$ установить $A_i = \lfloor \sqrt A_i \rfloor$. ($1 \le x \le y \le N$)
Входные данные
Первая строка содержит два целых числа $N$ и $Q$ — длина последовательности и количество запросов. ($1 \le N \le 100\,000$, $1 \le Q \le 500\,000$)
Вторая строка содержит $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 10^{18}$)
Следующие $Q$ строк содержат по одному запросу, как описано выше.
Выходные данные
Для каждого запроса типа 1 i выведите одну строку с результатом в порядке выполнения запросов.