E. Выбор вагона
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася любит ездить на поездах, но не любит, когда вагон, в котором он едет, расположен в хвосте.

Вася садится на поезд на вокзале. Поезд состоит из $$$n$$$ вагонов, пронумерованных от $$$1$$$ до $$$n$$$, считая от локомотива. Во время движения поезда происходит три типа событий:

  1. К голове поезда подцепляют некоторое количество вагонов;
  2. К хвосту поезда подцепляют некоторое количество вагонов;
  3. Вася пересчитывает величину, с помощью которой он оценивает удобство вагона (подробнее о ней ниже).

В каждый момент времени будем нумеровать вагоны с головы поезда, начиная с $$$1$$$. При добавлении новых вагонов к голове поезда нумерация старых может сдвинуться.

Чтобы выбрать, в каком вагоне ехать, Вася ввёл для каждого вагона величину $$$A_i$$$ (где $$$i$$$ — номер вагона), которая вычисляется следующим образом:

  • В начале поездки $$$A_i=0$$$, это также верно для новых вагонов в момент их добавления.
  • Во время очередного пересчёта Вася выбирает целые положительные числа $$$b$$$ и $$$s$$$ и прибавляет к $$$A_i$$$ величину $$$b + (i - 1) \cdot s$$$.

Вася ещё не решил, откуда и куда ехать, поэтому после каждого события одного из трёх типов он хочет знать номер наиболее близкого к голове поезда вагона из таких, что его значение $$$A_i$$$ минимально среди всех вагонов поезда. Так как вагонов очень много, Вася попросил Вас написать программу, отвечающую на его вопросы.

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

Первая строка содержит два целых числа $$$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}$$$.

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

После каждого из $$$m$$$ запросов выведите два целых числа: $$$j$$$ и $$$A_j$$$ — номер наиболее близкого к голове поезда вагона, что его значение $$$A_j$$$ минимально, и само значение $$$A_j$$$.

Пример
Входные данные
1 8
1 1
3 1 1
3 1 1
2 1
2 1
3 1 1
2 1
3 1 5
Выходные данные
1 0
1 1
1 2
3 0
3 0
1 3
5 0
1 4
Примечание
  • Изначально поезд состоит из одного вагона $$$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]$$$.