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.

7 6 6 1
3 1
4 2
4 5
6 3
6 5
6 2
6 6 1

24

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.

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

35
34
36
39
39