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

문제

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

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

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

입력

В первой строке записаны четыре целых числа $nn$, $mm$, $qq$, $kk$ ($1\le n1\; \backslash leq\; n$, $m\le 100000m\; \backslash leq\; 100\backslash ,000$, $1\le n\cdot m\le 10000001\; \backslash leq\; n\; \backslash cdot\; m\; \backslash leq\; 1\backslash ,000\backslash ,000$, $1\le q\le 1000001\; \backslash leq\; q\; \backslash leq\; 100\backslash ,000$, $1\le k\le {10}^{9}1\; \backslash leq\; k\; \backslash leq\; 10^9$) --- количество участников олимпиады, количество задач, количество событий и максимальный балл за каждую задачу соответственно.

Во второй строке записаны $mm$ целых чисел $s_1,s_2,\dots ,s_{m}s\_1,\; s\_2,\; \backslash ldots,\; s\_m$ ($0\le s_i\le k0\; \backslash leq\; s\_i\; \backslash leq\; k$), $ii$-е из которых задаёт количество баллов за тесты с offline-проверкой в $ii$-й задаче. Таким образом обычные тесты по $ii$-й задаче стоят $k-s_{i}k\; -\; s\_i$ баллов.

Далее следуют $nn$ строк по $mm$ целых чисел в каждой. Через $a_{i,j}a\_\{i,j\}$ обозначим $jj$-е число в $ii$-й строке ($0\le a_{i,j}\le k-s_{j}0\; \backslash leq\; a\_\{i,j\}\; \backslash leq\; k\; -\; s\_j$) --- количество баллов $ii$-го участника по $jj$-й задаче в предварительное таблице результатов.

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

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

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

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

출력

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

힌트

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

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

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

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