Зельда нашла способ соптимизировать создание эхо объектов и создала конвейер по их производству.
Конвейер работает почти что по принципу обычной очереди, но также обладает и некоторыми дополнительными функциями: например, если где-то в очереди скопилось много эхо, которые Зельде уже не понадобятся, есть способ их быстро из очереди изъять.
Более подробно, конвейер в каждый момент времени может быть разделен на несколько сегментов, содержащих отрезки подряд идущих элементов очереди. Для работы с конвейером доступны следующие операции:
Иными словами, порядок сохранившихся элементов в очереди не меняется, а при выполнении операции pop (2) помимо изъятия самого первого элемента очереди, также удаляются первые элементы каждого сегмента.
Для тестирования конвейера Зельда просит вас реализовать структуру данных, поддерживающую все эти операции.
В первой строке ввода даны целые числа $$$n$$$ и $$$q$$$ — изначальное количество элементов в очереди и число запросов ($$$1 \leq n, q \leq 10^5$$$).
Во второй строке ввода перечислены $$$n$$$ целых чисел $$$a_i$$$ — элементы очереди в ее начальном состоянии ($$$1 \leq a_i \leq 10^9$$$).
Далее следует $$$q$$$ запросов, по одному в каждой строке. Формат запросов в соответствии с их описанием в условии следующий: «push $$$x$$$», «pop», «cut $$$i$$$ $$$j$$$» и «restore» ($$$1 \leq x \leq 10^9$$$; $$$1 \leq i \leq S$$$, где $$$S$$$ — количество непустых сегментов в данный момент; $$$1 \leq j < C_S$$$, где $$$C_S$$$ — количество элементов в $$$S$$$-м сегменте).
Гарантируется, что все запросы корректны, в частности pop не вызывается при пустом первом сегменте, а cut не порождает пустые сегменты.
На каждый запрос pop выведите на отдельной строке вынимаемый первый элемент очереди.
Гарантируется, что хотя бы один такой запрос будет.
7 8 1 9 239 144 25 16 777 pop pop cut 1 2 pop restore pop pop pop
1 9 239 144 16 777
В первом примере из условия очередь претерпевает следующие изменения: