K. Циклический сдвиг отрезка

Дан массив. Обрабатывайте запросы двух видов: 1 l r k — циклически сдвинуть отрезок $[l, r]$ влево на $k$ позиций; 2 p — вывести элемент, стоящий на позиции $p$.

Сдвиг влево на $k$ означает, что элемент, стоявший на позиции $l + k$, оказывается на позиции $l$, а первые $k$ элементов отрезка уходят в его конец.

В первой строке — числа $n$ и $m$ ($1 \le n, m \le 10^5$). Во второй — $n$ чисел $a_i$ ($|a_i| \le 10^9$). Далее $m$ запросов; $1 \le l \le r \le n$, $0 \le k \le 10^9$, $1 \le p \le n$.

На каждый запрос второго вида выведите элемент в отдельной строке.