Train Car Selection
Contest: Codeforces Round 545 (Div. 1)
Difficulty rating: 2700
Tags: data structures, greedy

Vasya likes to travel by train, but doesn't like when the car he travels in is located in the tail of the train.

Vasya gets on the train at the station. The train consists of $$$n$$$ cars indexed from $$$1$$$ to $$$n$$$ counting from the locomotive (head of the train). Three types of events occur while the train is moving:

1. Some number of cars are added to the head of the train;
2. Some number of cars are added to the tail of the train;
3. Vasya recalculates the values of the convenience of the cars (read more about it below).

At each moment of time we will index the cars from the head of the train, starting from $$$1$$$. Note that when adding new cars to the head of the train, the indexing of the old ones may shift.

To choose which car to go in, Vasya will use the value $$$A_i$$$ for each car (where $$$i$$$ is a car index), which is calculated as follows:

- At the beginning of the trip $$$A_i=0$$$, as well as for the new cars at the time of their addition.
- During the next recalculation Vasya chooses some positive integers $$$b$$$ and $$$s$$$ and adds to all $$$A_i$$$ value $$$b + (i - 1) \cdot s$$$.

Vasya hasn't decided yet where he will get on the train and where will get off the train, so after each event of one of the three types he wants to know the least index of the car, such that its value $$$A_i$$$ is minimal. Since there is a lot of cars, Vasya asked you to write a program that answers his question.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^9$$$, $$$1 \leq m \leq 300\,000$$$), the number of cars in the train at the time of departure from the station and the number of stations, respectively.

Next $$$m$$$ lines contain the descriptions of events. Each event is one of the following three types:

- "$$$1$$$ $$$k$$$" ($$$1 \le k \le 10^9$$$), add $$$k$$$ cars to the head of the train
- "$$$2$$$ $$$k$$$" ($$$1 \le k \le 10^9$$$), add $$$k$$$ cars to the tail of the train
- "$$$3$$$ $$$b$$$ $$$s$$$" ($$$1 \le b, s \le 10^9$$$), recalculate the convenience of all train cars.

It is guaranteed that at any time the train length does not exceed $$$10^9$$$. Also it's guaranteed that the integers $$$A_i$$$ will not grow too high. Formally, it's guaranteed that if we sum the largest addition over all events of the $$$3$$$-rd type (that is, $$$b + (n - 1) \cdot s$$$, where $$$n$$$ is the number of cars at that moment) then the acquired sum would be at most $$$10^{18}$$$.

Output format:
After each of the $$$m$$$ queries print two integers: $$$j$$$ and $$$A_j$$$ — the number of the car closest to the head of the train, such that its value $$$A_j$$$ is minimal, and the value $$$A_j$$$ itself.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
- Initially the train consists of one car with $$$A_1 = 0$$$, let's denote train as $$$[0]$$$ for simplicity.
- After adding one car to the head, train is $$$[0, 0]$$$.
- After recalculation of values with parameters $$$b=1, s=1$$$, train is $$$[1, 2]$$$.
- After another recalculation of values with the parameters $$$b=1, s=1$$$, train is $$$[2, 4]$$$.
- After adding one car to the end, train is $$$[2, 4, 0]$$$.
- After another adding one car to the end, train is $$$[2, 4, 0, 0]$$$.
- After recalculation of values with parameters $$$b=1$$$, $$$s=1$$$, train is $$$[3, 6, 3, 4]$$$.
- After adding one car to the end, train is $$$[3, 6, 3, 4, 0]$$$.
- After recalculation of values with parameters $$$b=1$$$, $$$s=5$$$, train is $$$[4, 12, 14, 20, 21]$$$.

Example input:
1 8
1 1
3 1 1
3 1 1
2 1
2 1
3 1 1
2 1
3 1 5

Example output:
1 0
1 1
1 2
3 0
3 0
1 3
5 0
1 4

Editorial:
There are many approaches to this problem, many of them having $$$\mathcal{O}(q \log q)$$$ time, but we will describe a purely linear solution.
First, notice that for every group of cars added together, we need only to care about the first car in this group — the remaining ones will never be the answer.
Second, notice that there are some cars appended to the head of the train, then all previous cars will never be answer again, so we can simply replace them with cars with $$$A_i = 0$$$.
So now we only need to care about operations of adding cars to the tail, and about adding the progression.
Suppose cars located at positions $$$x$$$ and have comfort $$$A_x$$$.
Then observe the lower-left convex hull of points $$$(x, A_x)$$$. One can see, that the points not lying on this hull will never be an answer.
Also note, that we can handle all progressions implicitly — suppose the progressions are described with $$$b_i$$$, $$$s_i$$$. Then let's simply store current sums of $$$b_i$$$ and $$$s_i$$$. Then the operation of adding progression can be done by simply adding to those sums, also we don't have to track the moment the cars are added, since we can simply subtract from $$$A_i$$$ based on sums at the moment of addition.
So when we add cars to the end we simply need to add point to the end and possibly drop some points from the end of the current convex hull. And when we add new progression, we may also need to drop some elements from the hull, but since it's the convex hull, the line coefficients between neighboring points are monotonous, so we need to drop only some points in the end of the hull.