问题描述

Bronya 最近为阿拉哈托开发了一款小游戏，现在还在测试阶段。

游戏规则是这样的，有一张 $n\times m$ 的地图，左下角坐标为 $(1,1)$，右上角坐标为 $(n,m)$，其中有 $k$ 个位置是障碍物，其余位置是空地，你需要操作一个名为重装小兔的机器。每局游戏开始时，你首先需要在地图上为重装小兔指定一个起点（不能在障碍物上）。接下来可以向重装小兔发送命令，可选择的命令共有两个：

1. 向右移动： 假设当前坐标为 $(x,y)$，如果 $(x+1,y)$ 的位置仍是地图上的空地，则移动到 $(x+1,y)$ 并重复该过程，否则停止移动；
2. 向上移动： 假设当前坐标为 $(x,y)$，如果 $(x,y+1)$ 的位置仍是地图上的空地，则移动到 $(x,y+1)$ 并重复该过程，否则停止移动。

游戏目标是发送最少的命令使得重装小兔陷入无法移动的局面（即发送任何命令都无法改变位置）。

现在有一位名为“叱咤月海猫猫鱼”的玩家正在测试该游戏，她一共要进行 $q$ 次操作，操作共有两种：

1. 进行一局游戏，并选择 $(x,y)$ 作为起点（保证起点选择合法）。
2. 修改地图，选择一个空地 $(x,y)$，将该空地变为障碍物。

“叱咤月海猫猫鱼”希望你能告诉她，她所进行的每一局游戏在最优决策下最少需要发送几次命令，才能让重装小兔陷入无法移动的局面。

输入格式

第一行 $4$ 个正整数 $n,m,k,q$，其中 $n,m$ 表示地图的大小，$k$ 表示障碍物的数量，$q$ 表示操作次数。

接下来的 $k$ 行，每行两个正整数 $x,y$，表示坐标 $(x,y)$ 是障碍物，保证 $k$ 个坐标互不相同。

接下来的 $q$ 行，每行 $3$ 个正整数 $opt,x,y$。如果 $opt=1$ 则表示这次操作要进行一局游戏，选择起点为 $(x,y)$；如果 $opt=2$ 则表示这次操作要修改地图，将坐标为 $(x,y)$ 的空地变为障碍物。

输出格式

对于每次进行一局游戏的操作，输出一个整数，表示该局游戏在最优决策下最少需要发送几次命令，才能让重装小兔陷入无法移动的局面，每次回答独占一行。

样例输入

8 9 6 3
3 4
5 4
7 3
5 7
1 8
6 2
1 3 2
2 4 4
1 6 6

样例输出

4
2

数据范围

Subtask 1（10 pts）

$n,m,k,q\le 10$

Subtask 2（10 pts）

$n,m,q\le 10^3$，$k\le 5\times10^4$

Subtask 3（20 pts）

$n,m,k,q\le 10^5$，没有修改操作。

Subtask 4（20 pts）

$n,m,k,q\le 10^5$，保证修改的坐标在所有空白区域中等概率随机生成。

Subtask 5（40 pts）

$n,m,q,k\le 10^5$