D1. Параллельные вселенные (лёгкая)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Третий Доктор однажды правильно сказал, что путешествие между параллельными вселенными «подобно путешествию боком». Однако он ошибочно полагал, что существуют бесконечно много параллельных вселенных, тогда, как мы теперь все знаем, на самом деле их никогда не бывает больше 250.

Хайди недавно заполучила в свои руки инструмент для наблюдения за мультивселенной. Она смогла увидеть все $$$n$$$ вселенных, выстроенные в ряд, с несуществующими связями между ними. Она также заметила, что Доктор находился в $$$k$$$-й Вселенной.

Инструмент также указывает, что из-за ограничений, возникающих из пространственно-временного разрыва, число вселенных никогда не будет превышать $$$m$$$.

Очевидно, мультивселенная нестабильна из-за свободы воли. Каждый раз, когда кто-то принимает решение, происходит одно из двух: или создаётся параллельная мультивселенная, или ломается одна из несуществующих связей.

В частности,

  • Когда Вселенная создаётся, она встраивается или между двумя какими-то вселенными, или с одного из концов мультивселенной.
  • Когда ломается какая-то связь, это будет разрыв связи между двумя соседними вселенными. Таким образом, мультивселенная разбивается на два подотрезка, после чего подотрезок НЕ содержащий Доктора прекращает существовать.

Хайди хочет произвести симуляцию $$$t$$$ решений. Каждый раз, когда кто-то принимает какое-то решение, Хайди хочет знать длину мультивселенной (иначе говоря, число вселенных) и текущую позицию Доктора.

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

Первая строка содержит целые числа $$$n$$$, $$$k$$$, $$$m$$$ и $$$t$$$ ($$$2 \le k \le n \le m \le 250$$$, $$$1 \le t \le 1000$$$).

Каждая из следующих $$$t$$$ строк одного из следующих видов:

  • «$$$1$$$ $$$i$$$» ($$$1 \le i \le l + 1$$$), что обозначает что возникает новая вселенная на позиции $$$i$$$, где $$$l$$$ обозначает текущую длину мультивселенной.
  • «$$$0$$$ $$$i$$$» ($$$1 \le i \le l - 1$$$), что обозначает что $$$i$$$-я связь разрывается, где $$$l$$$ обозначает текущую длину мультивселенной.
Выходные данные

Выведите $$$t$$$ строк. Каждая строка должна содержать $$$l$$$ и $$$k$$$ — текущую длину мультивселенной и текущую позиция Доктора.

Гарантируется, что последовательность действий всегда будет корректной, иначе говоря, мультивселенная будет всегда размера не более $$$m$$$ и в момент разрыва связи будет хотя бы одна вселенная в мультивселенной.

Пример
Входные данные
5 2 10 4
0 1
1 1
0 4
1 2
Выходные данные
4 1
5 2
4 2
5 3
Примечание

В примере мультивселенная изначально состояла из 5 вселенных, а Доктор находился во второй из них.

На первом шаге сломалась связь номер 1, тем самым в мультивселенной осталось 4 вселенные, с Доктором находящимся в первой из них.

Затем добавилась новая вселенная с левом края мультивселенной, тем самым увеличив длину мультивселенной до 5, а Доктор находится во второй вселенной.

Затем сломалась крайняя справа связь.

И, наконец, добавилась новая вселенная между первой и второй вселенными.