Очередь за кымызом
У киоска с кымызом в Чолпон-Ате стоит очередь из n человек, у человека i в кошельке a[i] сомов. Кассир наблюдает за очередью и записывает события:
1 l r— люди сl-го поr-й (считая от начала очереди) поссорились и встали в обратном порядке;2 p x— послеp-го человека в очередь встал новый человек сxсомами (p = 0— в самое начало);3 p—p-й человек ушёл из очереди;4 l r— запрос: сколько денег у людей сl-го поr-й вместе;5 l r— запрос: сколько денег у самого богатого из людей сl-го поr-й.
Гарантируется, что все номера в событиях корректны для текущей очереди и очередь никогда не становится пустой.
Входные данные
В первой строке — n и q (1 ≤ n, q ≤ 2 · 10⁵). Во второй — n чисел a[i] (0 ≤ a[i] ≤ 10⁹). В каждой из следующих q строк — событие (0 ≤ x ≤ 10⁹).
Выходные данные
Для каждого запроса 4 и 5 выведите ответ в отдельной строке.
Пример 1
Вход:
5 6
3 1 4 1 5
1 1 3
2 0 9
4 1 3
3 2
1 1 5
5 1 2
Выход:
14
5
Пояснение
Очередь 3 1 4 1 5. После разворота людей 1…3 она становится 4 1 3 1 5, после 2 0 9 — 9 4 1 3 1 5, и сумма у людей 1…3 равна 14. После ухода второго (3 2) очередь 9 1 3 1 5, после разворота 1…5 — 5 1 3 1 9, и максимум у людей 1…2 равен 5.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n, q ≤ 1000.
Подсказка
Декартово дерево по неявному ключу поддерживает разрезания, склейки и отложенный разворот.
Комментарии