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

Представьте, что вы начали работать в крупной софтверной компании в качестве разработчика мощного текстового редактора. Современный текстовый редактор включает множество функций, но его разработка упрощается благодаря модульному подходу: функциональность редактора можно разделить на отдельные функции и библиотеки, которые могут разрабатываться отдельными командами или даже одним программистом.

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

Задача

Ваша задача — создать вспомогательную программу, которая будет в реальном времени подсчитывать количество строк в тексте, вводимом пользователем.

Входные данные

В первой строке входного файла указаны два натуральных числа, не превышающих 10^5: максимальное количество символов в строке L и общее количество операций с редактором N. Операция может быть одного из трех видов:

1. пользователь добавляет слово в конец текста;

2. пользователь добавляет слово в начало текста;

3. необходимо определить количество строк, занимаемых текущим текстом.

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

Выходные данные

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

Примеры

Оценивание

Подзадача Баллы Дополнительные ограничения Необходимыеподзадачи

0 0 Тесты из условия -

1 8 L ≤ 2 -

2 8 Суммарная длина всех введенных слов не превышает L -

3 7 N ≤ 1000 и во входном файле нет операций типа 2 -

4 14 Во входном файле нет операций типа 2 3

5 7 N ≤ 1000 и во входном файле нет операций типа 1 -

6 16 Во входном файле нет операций типа 1 5

7 7 N ≤ 1000 3, 5

8 33 Без дополнительных ограничений 0, 1, 2, 3, 4, 5, 6, 7