| Codeforces Round 263 (Div. 1) |
|---|
| Закончено |
У Яблова есть очень большой лист бумаги в форме прямоугольника размера 1 × n. Ваша задача — помочь Яблову свернуть этот лист. Для этого надо выполнить q запросов. Каждый запрос имеет один из следующих двух типов:
- Свернуть лист в позиции pi. После этого запроса левая часть листа размера 1 × pi должна оказаться над правой частью листа размера 1 × ([текущая ширина листа бумаги] - pi).
- Посчитать суммарную ширину листов бумаги, которые получатся, если сделать два вертикальных разреза описанным далее способом и учитывать только листы между этими разрезами. Один разрез проводится на расстоянии li от левой границы текущего листа бумаги, а другой разрез проводится на расстоянии ri от левой границы текущего листа бумаги.
Чтобы лучше понять описанные операции, посмотрите пояснение первого тестового примера.
В первой строке записано два целых числа: n и q (1 ≤ n ≤ 105; 1 ≤ q ≤ 105) — изначальная ширина листа бумаги и количество запросов.
В каждой из следующих q строк задан один из описанных запросов в следующем формате:
- «1 pi» (1 ≤ pi < [текущая ширина листа бумаги]) — запрос первого типа.
- «2 li ri» (0 ≤ li < ri ≤ [текущая ширина листа бумаги]) — запрос второго типа.
Для каждого запроса второго типа выведите ответ.
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
Ниже приведены иллюстрации, показывающие, какой формы будет лист бумаги после сворачивания в первом тестовом примере:
После первой операции сворачивания текущая ширина листа равна 4, после второй операции текущая ширина листа равна 2.
