CF1137E.Train Car Selection

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.

瓦西里喜欢乘坐火车旅行，但不喜欢自己乘坐的车厢位于列车尾部。

瓦西里在车站登上列车。列车由 $n$ 节车厢组成，车厢编号从 $1$ 到 $n$，编号顺序从车头（机车所在端）开始计数。列车运行过程中会发生以下三类事件：

1. 在列车车头添加若干节车厢；
2. 在列车车尾添加若干节车厢；
3. 瓦西里重新计算各车厢的“便利值”（具体定义见下文）。

在任意时刻，我们均从列车车头开始对车厢重新编号，编号从 $1$ 开始。注意：当在车头添加新车厢时，原有车厢的编号可能会发生改变。

为选择乘坐哪一节车厢，瓦西里将为每节车厢（编号为 $i$）定义一个值 $A_i$，其计算方式如下：

• 旅程开始时，所有车厢的 $A_i = 0$；新添加的车厢在其加入时刻的 $A_i$ 也为 $0$；
• 每次进行“重新计算”操作时，瓦西里选定两个正整数 $b$ 和 $s$，并将所有 $A_i$ 增加 $b + (i - 1) \cdot s$。

由于瓦西里尚未确定自己将在何处上车、何处下车，因此在每次发生上述三类事件之一后，他都想知道：当前所有车厢中，$A_i$ 值最小的车厢的最小编号是多少？由于车厢数量很多，瓦西里请你编写一个程序来回答他的问题。

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}$.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^9$，$1 \leq m \leq 300\,000$），分别表示列车在车站出发时的车厢数量和车站总数。

接下来 $m$ 行描述了各事件。每个事件为以下三种类型之一：

• “$1$ $k$”（$1 \le k \le 10^9$）：在列车头部添加 $k$ 节车厢；
• “$2$ $k$”（$1 \le k \le 10^9$）：在列车尾部添加 $k$ 节车厢；
• “$3$ $b$ $s$”（$1 \le b, s \le 10^9$）：重新计算所有列车车厢的便利值。

保证在任意时刻列车长度均不超过 $10^9$。同时保证整数 $A_i$ 不会增长过高。形式化地说，若对所有第 $3$ 类事件，将该事件发生时的最大加法项（即 $b + (n - 1) \cdot s$，其中 $n$ 为该时刻车厢数）求和，则所得总和至多为 $10^{18}$。

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.

在每次 $m$ 个查询之后，输出两个整数：$j$ 和 $A_j$ —— 其中 $j$ 是距离列车车头最近的车厢编号，且该车厢的值 $A_j$ 为最小值；$A_j$ 即为该最小值本身。

• 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]$.

• 最初列车仅包含一节车厢，其值为 $A_1 = 0$，为简便起见，我们将该列车记作 $[0]$。

• 在车头添加一节车厢后，列车变为 $[0, 0]$。

• 使用参数 $b=1, s=1$ 重新计算各车厢数值后，列车变为 $[1, 2]$。

• 再次使用参数 $b=1, s=1$ 重新计算各车厢数值后，列车变为 $[2, 4]$。

• 在车尾添加一节车厢后，列车变为 $[2, 4, 0]$。

• 再次在车尾添加一节车厢后，列车变为 $[2, 4, 0, 0]$。

• 使用参数 $b=1$, $s=1$ 重新计算各车厢数值后，列车变为 $[3, 6, 3, 4]$。

• 在车尾添加一节车厢后，列车变为 $[3, 6, 3, 4, 0]$。

• 使用参数 $b=1$, $s=5$ 重新计算各车厢数值后，列车变为 $[4, 12, 14, 20, 21]$。