Разморозка таблицы

Только что завершился очный этап Открытой олимпиады школьников по программированию. В очном этапе принимало участие $n$ школьников, для решения было предложено $m$ задач (разумеется, интересных), за каждую задачу можно было получить любое количество баллов от $0$ до $k$ включительно. В некоторых задачах есть тесты с offline-проверкой, это означает, что результаты тестирования решения на данных тестах станут доступны только после окончания соревнования. В этот раз правила тестирования всех задач таковы, что решения будут выполняться на тестах с offline-проверкой только при прохождении всех обычных тестов (что, вообще говоря, не всегда верно для задач Открытой олимпиады).

Сейчас все школьники собрались в одном зале и ожидают начала церемонии закрытия. Публично доступна предварительная таблица результатов, в которой баллы всех школьников по всем задачам указаны без учёта баллов за тесты с offline-проверкой. При этом каждый из участников олимпиады знает свои итоговые баллы по всем задачам, то есть баллы с учётом тестов с offline-проверкой. Время от времени кто-либо из участников сообщает всем присутствующим свои баллы по какой-либо задаче, а некоторые из участников задаются вопросом, какое максимальное и какое минимальное место они могли занять с учётом предварительной таблицы и всей информации, сообщённой к данному моменту другими участниками.

Местом участника называется количество участников, набравших строго большее количество баллов чем он, увеличенное на один. Когда кто-либо из участников хочет выяснить своё максимальное и минимальное возможное итоговое место, он рассматривает все возможные итоговые таблицы, которые могли получиться с учётом 1) имеющейся предварительной таблицы, 2) информации, сообщённой другими участниками, и 3) правилами тестирования задач. Последнее означает, что баллы за offline-проверку можно получить, только набра полный балл по обычным тестам.

В первой строке записаны четыре целых числа $n$, $m$, $q$, $k$ ($1 \leq n$, $m \leq 100\,000$, $1 \leq n \cdot m \leq 1\,000\,000$, $1 \leq q \leq 100\,000$, $1 \leq k \leq 10^9$) --- количество участников олимпиады, количество задач, количество событий и максимальный балл за каждую задачу соответственно.

Во второй строке записаны $m$ целых чисел $s_1, s_2, \ldots, s_m$ ($0 \leq s_i \leq k$), $i$-е из которых задаёт количество баллов за тесты с offline-проверкой в $i$-й задаче. Таким образом обычные тесты по $i$-й задаче стоят $k - s_i$ баллов.

Далее следуют $n$ строк по $m$ целых чисел в каждой. Через $a_{i,j}$ обозначим $j$-е число в $i$-й строке ($0 \leq a_{i,j} \leq k - s_j$) --- количество баллов $i$-го участника по $j$-й задаче в предварительное таблице результатов.

Далее следуют $q$ строк с описанием событий. Каждая строка начинается с целого числа $t$ ($1 \leq t \leq 2$) --- типа события.

Если $t=1$, то далее следует одно целое число $i$ ($1 \leq i \leq n$), которое означает, что участник с номером $i$ хочет узнать своё максимальное и минимальное возможное место в итоговой таблице.

Если $t=2$, то далее следуют три целых числа $i$, $j$, $c$ ($1 \leq i \leq n$, $1 \leq j \leq m$, $a_{i,j} \leq c \leq k$), которые означают, что участник с номером $i$ объявил всем, что его баллы по задаче $j$ равны $c$.

Гарантируется, что никакой участник не называет баллы по одной и той же задаче дважды, и что участник называет свои баллы по задаче только при условии, что он набрал по ней максимально возможный балл без учёта тестов с offline-проверкой. Дополнительно гарантируется, что во входных данных присутствует хотя бы один запрос первого типа.

Для каждого запроса первого типа выведите два целых числа --- максимальное и минимальное место, которое мог занять данный участник, согласно имеющейся на текущий момент времени информации.

В первом тесте из условия оба участника делят первое место.

Во втором тесте из условия первый участник может набрать ещё $10$ баллов, но даже если этого не произойдёт, он останется на первом месте. Баллы второго участника измениться не могут и он занимает второе место.

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

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