题目描述

有一个 $n$ 行 $m$ 列的网格，初始时每一个格子都是白色。露米娅需要用 $k$ 种不同的颜色（包括白色）对这个网格涂色 $q$ 次，涂色的规则是：露米娅可以选择任意一种颜色，将某一整行（或某一整列）涂上这种颜色，该行（或该列）格子原有的颜色都会被覆盖成新涂上的颜色。请你算一算涂完色后网格上最多会出现几种不同的颜色。

注：涂色的位置和顺序是固定的，但露米娅可以自由决定每次使用哪种颜色。

输入格式

第一行包含四个整数 $n, m, k, q$，分别表示网格的行数、列数，颜色的种类数以及露米娅进行涂色操作的次数。

接下来 $q$ 行，每行包含两个整数 $op_i, x_i$，表示一次操作。

如果 $op_i = 0$，那么这次操作会将第 $x_i$ 行涂色。

如果 $op_i = 1$，那么这次操作会将第 $x_i$ 列涂色。

输出格式

输出一行一个整数表示答案。

3 3 3 2
0 1
1 1

3

2 1 10 1
1 1

1

大样例

大样例

数据规模与约定

对于所有测试点：$1 ≤ n, m, k, q ≤ 2 × 10^5$

每个测试点的具体限制见下表：