时间限制:C/C++/Rust/Pascal 5秒,其他语言10秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
Oshwiciqwq studies Physics in a shabby classroom in his sophomore year. The classroom has
rows and
columns of seats, which are narrowly set like a matrix. There is a huge screen in the front of the classroom.
The whole classroom can be seen as a plane, and every seat can be seen as a point on it. The set of all seats' coordinates is
. Additionally, the screen can be seen as a segment, with two endpoints at
and
.
As a student who loves studying, he always wants to seat in the front row, so that he can see the whole screen clearly. He thinks a seat is good if and only if there are no other people blocking him from seeing the whole screen. Formally, the seat at
is good if and only if there is no other person sitting on the seat that is on the segment between
and any point on the segment
(including endpoints).
However, today he arrived at the classroom as early as usual, only to find
people had already taken their seats. What's worse, while he was busy searching for a good seat, some people changed their seats one by one. Totally there are
events of changing seats. He is extremely anxious now, so could you please help him count how many seats are good after each of the
changing events?
Obviously, a seat can only be occupied by at most one person at the same time.
输入描述:
The first line contains four integers
(
), denoting the number of rows, the number of columns, the number of people already taken seats and the number of changing events.
For the
-th line in the following
lines, there are two integers
(
), denoting the coordinates of an occupied seat.
For the
-th line in the following
lines, there are three integers
(
), denoting the id of person changing seats and the coordinates of a seat that the person will change to.
It is guaranteed that any coordinate appears only once in the input.
输出描述:
The output contains
lines.
For each of the
changing events, print an integer in a single line, denoting the number of good seats at that time.
示例1
输入
复制
7 6 6 1
3 1
4 2
4 5
6 3
6 5
6 2
6 6 1
说明
The first sample is shown in the graph. The segment on the

-axis denotes the screen. The rectangular area denotes all the seats. After the changing event, the red points are the occupied seats while the green points are good seats.
This is an example of a non-good seat. For the seat at
)
, the segment between it and
)
on the screen contains a occupied seat at
)
, so it is not a good seat.
示例2
输入
复制
10 10 5 5
4 10
5 9
4 2
6 5
4 7
3 3 5
2 4 1
3 3 6
2 10 6
5 7 4