순위표 동결 해제

오픈 올림피아드의 현장 단계가 방금 끝났다. 이 단계에는 $n$명의 학생이 참가했고, $m$개의 문제가 출제되었다. 각 문제의 점수는 $0$ 이상 $k$ 이하의 정수다. 일부 문제에는 오프라인 채점 테스트가 있으며, 그 결과는 대회가 끝난 뒤에야 공개된다. 이번 대회에서는 제출물이 일반 테스트를 모두 통과한 경우에만 오프라인 채점 테스트가 실행된다. 이는 오픈 올림피아드의 모든 문제에 항상 해당하는 것은 아니다.

지금 모든 학생이 한 홀에 모여 폐회식을 기다리고 있다. 공개된 예비 순위표에는 모든 학생의 문제별 점수가 적혀 있으며, 오프라인 채점 점수는 빠져 있다. 각 학생은 오프라인 채점 점수를 포함한 자신의 최종 점수를 알고 있다. 학생들은 때때로 특정 문제에서 받은 점수를 모두에게 알린다. 일부 학생은 예비 순위표와 지금까지 알려진 정보를 바탕으로 자신이 가능한 최고 등수와 최저 등수를 알고 싶어 한다.

등수는 자신보다 점수가 엄격히 높은 참가자의 수에 1을 더한 값이다. 학생이 최종 등수의 최고와 최저를 구할 때는 1) 예비 순위표, 2) 다른 학생들이 알린 정보, 3) 채점 규칙과 모두 맞아떨어지는 모든 최종 순위표를 고려한다. 채점 규칙에 따라 오프라인 채점 점수는 일반 테스트에서 만점을 받은 경우에만 얻을 수 있다.

첫 줄에는 네 정수 $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$)이 주어진다. $s_i$는 $i$번째 문제의 오프라인 채점 점수다. 따라서 $i$번째 문제의 일반 테스트 점수는 $k - s_i$점이다.

이어서 $n$개의 줄에 각각 $m$개의 정수가 주어진다. $a_{i,j}$는 $i$번째 줄의 $j$번째 수이며 ($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$점이라고 모두에게 알린다는 뜻이다.

같은 학생이 같은 문제의 점수를 두 번 알리는 경우는 없다. 학생은 오프라인 채점을 제외한 점수에서 해당 문제의 최대 점수를 받은 뒤에만 그 점수를 알린다. 종류 1 질의는 최소 하나 있다고 보장된다.

종류 1 이벤트마다, 그 시점까지의 정보로 해당 학생이 가질 수 있는 최고 등수와 최저 등수를 공백으로 구분해 한 줄에 출력한다.

첫 번째 테스트에서 두 참가자는 1등을 나눠 가진다.

두 번째 테스트에서 첫 번째 참가자는 10점을 더 받을 수 있지만, 받지 않더라도 1등을 유지한다. 두 번째 참가자의 점수는 바뀔 수 없으므로 2등이다.

세 번째 테스트에서 각 참가자는 190점에서 200점 사이의 점수를 받을 수 있으며, 그 점수에 따라 1등이 되거나 2등이 된다.

네 번째 테스트는 각 참가자가 최종 점수를 알리기 전까지 세 번째 테스트와 같다. 알린 뒤에는 등수가 하나로 정해진다.