| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
Только что завершился очный этап Открытой олимпиады школьников по программированию. В очном этапе принимало участие $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-проверкой. Дополнительно гарантируется, что во входных данных присутствует хотя бы один запрос первого типа.
Для каждого запроса первого типа выведите два целых числа --- максимальное и минимальное место, которое мог занять данный участник, согласно имеющейся на текущий момент времени информации.
2 2 2 100 0 0 100 100 100 100 1 1 1 2
1 1 1 1
2 2 2 100 10 0 90 100 89 100 1 1 1 2
1 1 2 2
2 2 2 100 10 0 90 100 90 100 1 1 1 2
1 2 1 2
2 2 6 100 10 0 90 100 90 100 1 1 1 2 2 1 1 90 2 2 1 100 1 1 1 2
1 2 1 2 2 2 1 1
В первом тесте из условия оба участника делят первое место.
Во втором тесте из условия первый участник может набрать ещё 10ドル$ баллов, но даже если этого не произойдёт, он останется на первом месте. Баллы второго участника измениться не могут и он занимает второе место.
В третьем тесте из условия каждый из участников может набрать от 190ドル$ до 200ドル$ баллов и, в зависимости от этого, занять либо первое, либо второе место.
В четвёртом тесте из условия ситуация аналогична третьему тесту до тех пор, пока каждый из участников не объявит свои итоговые баллы. После этого места определяются однозначно.