Текстовий редактор

Уявіть, що вас узяли на роботу у велику софтверну компанію і ви стали розробником потужного текстового редактора. Звичайно, сучасний текстовий редактор містить величезну кількість функцій, однак його розробку спрощує загальний підхід: усю функціональність редактора можна розбити на окремі функції й бібліотеки, розробка кожної з яких під силу окремій команді розробників чи навіть одному програмісту..

Текст формується таким чином: користувач щоразу додає по одному слову або в кінець, або на початок тексту, відбиваючи це слово пробілом від попередніх чи від наступних слів. Один рядок вікна текстового редактора вміщає не більше ніж $L$ символів (якщо рахувати й пробіли). Редактор втілює стандартну логіку перенесення рядків: перше слово, яке не вміщається в попередній рядок, переноситься в наступний. Якщо два сусідніх слова розташовані в різних рядках, пробіл між ними зникає.

Завдання

Ваша задача — реалізувати допоміжну програму, що в режимі реального часу рахуватиме кількість рядків у тексті, який вводить користувач

Вхідні дані

У першому рядку вхідного файлу містяться два натуральних числа, які не перевищують $10^5$: максимальна кількість символів у рядку $L$ та загальна кількість операцій із редактором $N$, причому під операцією ми розуміємо дію одного з трьох видів:

1. користувач додає слово в кінець тексту;

2. користувач додає слово на початок тексту;

3. потрібно знайти кількість рядків, які займає поточний текст.

Далі йдуть $N$ рядків по одному або два числа в кожному: тип операції (1, 2 або 3) і, для операцій 1 та 2 (введення слова), через пробіл довжина слова, яке ввів користувач. Ця довжина є натуральним числом, що не може перевищувати максимальну довжину рядка $L$. Перша операція у вхідному файлі може бути лише операцією типу 1 або операцією типу 2, які слід тлумачити однаково: це введення першого слова у порожній до того текст. Також відомо, що у вхідному файлі є щонайменше одна операція типу 3.

Вихідні дані

Вихідний файл повинен містити стільки рядків, скільки операцій типу 3 задано у вхідному файлі. У кожному з них потрібно надати результат на відповідний запит — поточну на момент запиту кількість рядків у тексті.

Приклади

Примітка

Після введення всіх слів у першому рядку тексту міститимуться слова довжин 1 і 6, у другому рядку слова довжин 3 і 5, а у третьому — одне слово довжини 1.

Оцінювання

1. ($8$ балів): $L\le 2$;

2. ($8$ балів): Сумарна довжина всіх уведених слів не перевищує $L$;

3. ($7$ балів): $N\le 1000$ та у вхідному файлі немає операцій типу 2;

4. ($14$ балів): У вхідному файлі немає операцій типу 2;

5. ($7$ балів): $N\le 1000$ та у вхідному файлі немає операцій типу 1;

6. ($16$ балів): У вхідному файлі немає операцій типу 1;

7. ($7$ балів): $N\le 1000$;

8. ($33$ бали): Без додаткових обмежень.