Вася любит ездить на поездах, но не любит, когда вагон, в котором он едет, расположен в хвосте.
Вася садится на поезд на вокзале. Поезд состоит из \(n\) вагонов, пронумерованных от \(1\) до \(n\), считая от локомотива. Во время движения поезда происходит три типа событий:
- К голове поезда подцепляют некоторое количество вагонов;
- К хвосту поезда подцепляют некоторое количество вагонов;
- Вася пересчитывает величину, с помощью которой он оценивает удобство вагона (подробнее о ней ниже).
В каждый момент времени будем нумеровать вагоны с головы поезда, начиная с \(1\). При добавлении новых вагонов к голове поезда нумерация старых может сдвинуться.
Чтобы выбрать, в каком вагоне ехать, Вася ввёл для каждого вагона величину \(A_i\) (где \(i\) — номер вагона), которая вычисляется следующим образом:
- В начале поездки \(A_i=0\), это также верно для новых вагонов в момент их добавления.
- Во время очередного пересчёта Вася выбирает целые положительные числа \(b\) и \(s\) и прибавляет к \(A_i\) величину \(b + (i - 1) \cdot s\).
Вася ещё не решил, откуда и куда ехать, поэтому после каждого события одного из трёх типов он хочет знать номер наиболее близкого к голове поезда вагона из таких, что его значение \(A_i\) минимально среди всех вагонов поезда. Так как вагонов очень много, Вася попросил Вас написать программу, отвечающую на его вопросы.
Выходные данные
После каждого из \(m\) запросов выведите два целых числа: \(j\) и \(A_j\) — номер наиболее близкого к голове поезда вагона, что его значение \(A_j\) минимально, и само значение \(A_j\).