L. Вырезать и вклеить

Дан массив. Обрабатывайте запросы двух видов:

• 1 l r p — вырезать отрезок $[l, r]$ и вставить его обратно так, чтобы его первый элемент оказался на позиции $p$ в массиве после удаления отрезка ($1 \le p \le n - (r - l + 1) + 1$);
• 2 l r — вывести сумму на отрезке $[l, r]$.

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

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