Ice Skating

题目描述

Maru the golden retriever is passionate about ice skating—he lives for the thrill of gliding at breakneck speed across the rink. Unfortunately, his enthusiasm far exceeds his skill. Maru's control is... questionable at best (possibly because he normally uses all four of his legs). More often than not, he ends up crashing into obstacles or launching himself spectacularly off the edge of the rink.

The rink can be described as a grid of $n$ rows and $m$ columns, and we use $(r,c)$ to denote the cell on the $r$-th row and the $c$-th column. Thus $(1,1)$ is the upper-left corner, and $(n,m)$ is the bottom-right corner. Initially, there are $k$ obstacles on the rink where the $i$-th obstacle is on the cell $(x_i,y_i)$, and all the remaining $n\times m-k$ cells are empty.

If Maru is currently at $(a,b)$, he has two options to move:

• Skate right: Keep moving right until meeting an obstacle or the boundary of the rink. That is, if $(a,b+1)$ is within the rink and there is no obstacle on it, Maru will move to $(a,b+1)$ and repeat checking this condition; otherwise, he stops moving.
• Skate down: Keep moving down until meeting an obstacle or the boundary of the rink. That is, if $(a+1,b)$ is within the rink and there is no obstacle on it, Maru will move to $(a+1,b)$ and repeat checking this condition; otherwise, he stops moving.

Notice that, regardless of how far Maru moves in one option, it is considered one move.

Maru doesn't have much energy left, because his humans refused to give him a second breakfast; he wants to know the minimum number of moves to reach a "stable position". A "stable position" is a position where he cannot move to another position, no matter how he chooses to move next.

You need to support $q$ operations, each of which belongs to one of the following two types:

• 1 a b: A query for the minimum number of moves to reach a "stable position", if Maru starts his skating at $(a,b)$. It's guaranteed that there is no obstacle on cell $(a,b)$.
• 2 a b: Put an obstacle on cell $(a,b)$. It's guaranteed that there is no obstacle on cell $(a,b)$ before this operation.

输入格式

The first line contains four integers $n,m,k,q~(1\le n,m,k,q\le 10^5)$, representing the size of the rink, the number of obstacles initially, and the number of operations.

In the following $k$ lines, each line contains two integers $x_i,y_i~(1\le x_i\le n, 1\le y_i\le m)$, representing the position of the $i$-th obstacle. It's guaranteed that the positions of obstacles are pairwise distinct.

In the following $q$ lines, each line contains three integers $op_i, a_i, b_i~(op_i\in \{1,2\}, 1\le a_i\le n, 1\le b_i\le m)$, representing the $i$-th operation.

输出格式

For each query, output a single line with a single integer, representing the answer.

样例输入 #1

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

样例输出 #1

2

提示

The image below shows one possible answer to each query in the example.