У Яблова есть очень большой лист бумаги в форме прямоугольника размера 1 × n. Ваша задача — помочь Яблову свернуть этот лист. Для этого надо выполнить q запросов. Каждый запрос имеет один из следующих двух типов:
Чтобы лучше понять описанные операции, посмотрите пояснение первого тестового примера.
В первой строке записано два целых числа: n и q (1 ≤ n ≤ 105; 1 ≤ q ≤ 105) — изначальная ширина листа бумаги и количество запросов.
В каждой из следующих q строк задан один из описанных запросов в следующем формате:
Для каждого запроса второго типа выведите ответ.
Ниже приведены иллюстрации, показывающие, какой формы будет лист бумаги после сворачивания в первом тестовом примере:
После первой операции сворачивания текущая ширина листа равна 4, после второй операции текущая ширина листа равна 2.
7 4 1 3 1 2 2 0 1 2 1 2
4 3
10 9 2 2 9 1 1 2 0 1 1 8 2 0 8 1 2 2 1 3 1 4 2 2 4
7 2 10 4 5
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач