题目描述

开放奥林匹克程序设计竞赛决赛阶段刚刚结束。决赛共有 $n$ 名学生参加，比赛共有 $m$ 道题。每道题都可以获得从 $0$ 到 $k$ 的任意整数分。

某些题目中存在 offline 检查测试，这意味着这些测试的评测结果只有在比赛结束后才会公布。本次比赛中，所有题目的评测规则都是：只有通过了全部普通测试，才会运行 offline 检查测试。（一般来说，开放奥林匹克的题目并不总是这样。）

现在所有学生都聚集在一个大厅里，等待闭幕式开始。当前公开可见的是初步榜单，其中每个学生每道题的分数都不包含 offline 检查测试的分数。同时，每个参赛者都知道自己每道题的最终分数，也就是包含 offline 检查测试后的分数。

不时会有参赛者向所有人公布自己某道题的最终分数。也有一些参赛者会想知道：在当前初步榜单和目前为止其他人公布的信息下，自己在最终榜单中可能获得的最高名次和最低名次分别是多少。

一名参赛者的名次定义为：总分严格高于他的参赛者数量再加 $1$。

当某位参赛者想知道自己的最高和最低可能名次时，他会考虑所有可能的最终榜单。这些榜单必须同时满足：

1. 当前公开的初步榜单；
2. 目前为止其他参赛者公布的信息；
3. 各题的评测规则，即只有普通测试拿满分时才可能获得 offline 检查测试分数。

输入格式

第一行包含四个整数 $n,m,q,k$，分别表示参赛者数量、题目数量、事件数量以及每道题最高分。

$$1 \le n,m \le 100000,\quad 1 \le n\cdot m \le 1000000,\quad 1 \le q \le 100000,\quad 1 \le k \le 10^9$$

第二行包含 $m$ 个整数 $s_1,s_2,\ldots,s_m$，其中 $s_i$ 表示第 $i$ 题 offline 检查测试的分数。因此第 $i$ 题普通测试的分数为 $k-s_i$。

$$0 \le s_i \le k$$

接下来 $n$ 行，每行包含 $m$ 个整数。令 $a_{i,j}$ 表示第 $i$ 行第 $j$ 个数，即第 $i$ 名参赛者在初步榜单中第 $j$ 题的分数。

$$0 \le a_{i,j} \le k-s_j$$

接下来 $q$ 行，每行描述一个事件。每行开头是一个整数 $t$，表示事件类型。

$$1 \le t \le 2$$

• 如果 $t=1$，接下来有一个整数 $i$，表示编号为 $i$ 的参赛者想知道自己的最高和最低可能名次。

  $$1 \le i \le n$$

• 如果 $t=2$，接下来有三个整数 $i,j,c$，表示编号为 $i$ 的参赛者向所有人公布自己第 $j$ 题的最终分数为 $c$。

  $$1 \le i \le n,\quad 1 \le j \le m,\quad a_{i,j} \le c \le k$$

保证没有参赛者会两次公布同一道题的分数。并且，参赛者只会在自己该题普通测试已经拿到不含 offline 检查的满分时，才会公布该题成绩。

额外保证，输入中至少存在一个第一类查询。

输出格式

对于每个第一类查询，输出两个整数，分别表示根据当前信息，该参赛者可能获得的最大名次和最小名次。

样例 1

输入

2 2 2 100
0 0
100 100
100 100
1 1
1 2

输出

1 1
1 1

样例 2

输入

2 2 2 100
10 0
90 100
89 100
1 1
1 2

输出

1 1
2 2

样例 3

输入

2 2 2 100
10 0
90 100
90 100
1 1
1 2

输出

1 2
1 2

样例 4

输入

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$ 的总分，因此根据实际情况，他们可能排名第一或第二。

第四个样例中，在每名参赛者都公布自己的最终成绩前，情况与第三个样例类似。公布后，名次被唯一确定。

评分方式

本题共有若干组测试。每组分数只有在通过该组所有测试以及表中指定的部分前置测试组后才会获得。Offline 检查表示该组测试结果只会在比赛结束后公布。

组别	分数	$n,m$ 限制	事件类型限制	必须先通过的组	说明
0		-	-	-	样例测试
1	30	$1 \le n,m \le 1000$		0	-
2		-	所有事件均满足 $t=1$
3	40		-	0, 1, 2	Offline 检查