Text Editor
Imagine you've been hired by a large software company to develop a powerful text editor. A modern text editor boasts numerous features, but its development is streamlined by a general approach: all functionalities can be divided into separate functions and libraries, each handled by a different team or even a single programmer.
The text is constructed as follows: the user adds one word at a time, either to the end or the beginning of the text, with a space separating it from the adjacent words. A single line in the text editor window can accommodate no more than L characters, including spaces. The editor uses standard line-wrapping logic: the first word that doesn't fit on the current line is moved to the next. If two consecutive words are split across lines, the space between them is removed.
Task
Your task is to create a program that counts the number of lines in the text as it is entered by the user in real-time.
Input Data
The first line of the input file contains two natural numbers, each not exceeding 10^5: the maximum number of characters per line L and the total number of operations N with the editor. An operation can be one of three types:
The user adds a word to the end of the text.
The user adds a word to the beginning of the text.
Determine the number of lines currently occupied by the text.
The next N lines each contain one or two numbers: the type of operation (1, 2, or 3) and, for operations 1 and 2 (word input), the length of the word being added. This length is a natural number that does not exceed the maximum line length L. The first operation in the input file can only be of type 1 or type 2, which should be treated the same: it represents the addition of the first word to an initially empty text. It is guaranteed that there is at least one operation of type 3 in the input file.
Output Data
The output file should contain as many lines as there are operations of type 3 in the input file. Each line should display the result for the corresponding query — the current number of lines in the text at the time of the query.
Evaluation
Subtask Points Additional Constraints Required Subtasks
0 0 Tests from the condition -
1 8 L ≤ 2 -
2 8 The total length of all entered words does not exceed L -
3 7 N ≤ 1000 and there are no operations of type 2 in the input file -
4 14 There are no operations of type 2 in the input file 3
5 7 N ≤ 1000 and there are no operations of type 1 in the input file -
6 16 There are no operations of type 1 in the input file 5
7 7 N ≤ 1000 3, 5
8 33 No additional constraints 0, 1, 2, 3, 4, 5, 6, 7