Kitties
Description
Marcos is a veterinarian and cats are his favorite animal. So much so, that for a few years now he has had a pet shop called Kitties, where he sells all kinds of things for cats. In his shop, there is also a screen of height $H_1$ and width $W$ that displays a website that Marcos created, with different kitten pictures that get renewed from time to time.
The website consists of a vertically scrollable panel, which has the same width $W$ as the screen, but has a greater height $H_2 > H_1$ (that is why it is vertically scrollable).
Initially, the panel contains $N$ kitten pictures placed in different positions. $K$ new pictures will appear later, so there are $N+K$ possible different pictures in total.
The $i$-th of these pictures is identified with the positive integer $i$, called its id. Pictures with id from $1$ to $N$ are the initial ones, and pictures with id $N+1$ to $N+K$ will be added later. For each $i$ from $1$ to $N+K$, the picture with id $i$ covers a rectangular portion of the panel defined by the following values:
- $U_i$: the distance from the top edge of the panel to the top edge of the picture
- $D_i$: the distance from the top edge of the panel to the bottom edge of the picture
- $L_i$: the distance from the left edge of the panel to the left edge of the picture
- $R_i$: the distance from the left edge of the panel to the right edge of the picture
As the panel is bigger than the screen, then only a subrectangle of it will be visible at all times. Similar to the pictures, such subrectangle is defined by the values $s_U, s_D, s_L$ and $s_R$.
Initially, the scroll position of the website is $x=0$, meaning that the subrectangle of the panel visible in the screen is $s_U = 0$, $s_D = H_1$, $s_L = 0$, $s_R = W$. However, the website is programmed so that from time to time, some new pictures appear, others disappear, and the scroll position changes.
Marcos is afraid that these changes programmed to happen automatically could affect the efficiency of the website, as the pictures are loaded and removed from memory depending on whether they are visible or not. And that's why he needs your help.
Given $Q$ changes that happen on the website in order, for each of them you have to answer the following two questions:
- How many pictures that were not visible (partially or completely) before this change, will be visible after the change?
- How many pictures that were visible (partially or completely) before this change, will not be visible after the change?
A first line with five integers $N$, $Q$, $H_1$, $H_2$ and $W$ ($1 \leq N, Q \leq 10^5$, $1 \leq H_1, H_2, W \leq 10^9$, $H_1 < H_2$) explained in the statement.
Then $N$ lines follow. The $i$-th of these lines contains four integers $U_i$, $D_i$, $L_i$ and $R_i$, describing the location in the panel of the picture with id $i$.
Then $Q$ lines follow that represent the changes that happen on the website in order. Each of these $Q$ lines has a character followed by a number of integers, according to one of the following formats:
- A $j$ $U_j$ $D_j$ $L_j$ $R_j$: indicating that a new picture appears with id $j$, located in the panel as indicated by $U_j$, $D_j$, $L_j$ and $R_j$. The $i$-th change of this type in the input will have $j=N+i$, and there will be $K$ changes of this type in total.
- D $j$ $(1 \leq j \leq N+K)$: indicating that the picture with id $j$ disappears (it is guaranteed that this picture is present in the panel).
- M $x$ $(0 \leq x \leq H_2-H_1)$: indicating that the scroll position is modified to take the value $x$, meaning that the subrectangle of the panel that is displayed in the screen changes to be $s_U = x$, $s_D = x+H_1$, $s_L = 0$, $s_R = W$
It is guaranteed that the pictures don't overlap nor touch each other, and for all $i$ from $1$ to $N+K$, $0 \leq U_i < D_i \leq H_2$, $0 \leq L_i < R_i \leq W$.
$Q$ lines, one for each change given in the input, with two integers answering the two questions present in the statement, in the order in which these questions were asked.
Input
A first line with five integers $N$, $Q$, $H_1$, $H_2$ and $W$ ($1 \leq N, Q \leq 10^5$, $1 \leq H_1, H_2, W \leq 10^9$, $H_1 < H_2$) explained in the statement.
Then $N$ lines follow. The $i$-th of these lines contains four integers $U_i$, $D_i$, $L_i$ and $R_i$, describing the location in the panel of the picture with id $i$.
Then $Q$ lines follow that represent the changes that happen on the website in order. Each of these $Q$ lines has a character followed by a number of integers, according to one of the following formats:
- A $j$ $U_j$ $D_j$ $L_j$ $R_j$: indicating that a new picture appears with id $j$, located in the panel as indicated by $U_j$, $D_j$, $L_j$ and $R_j$. The $i$-th change of this type in the input will have $j=N+i$, and there will be $K$ changes of this type in total.
- D $j$ $(1 \leq j \leq N+K)$: indicating that the picture with id $j$ disappears (it is guaranteed that this picture is present in the panel).
- M $x$ $(0 \leq x \leq H_2-H_1)$: indicating that the scroll position is modified to take the value $x$, meaning that the subrectangle of the panel that is displayed in the screen changes to be $s_U = x$, $s_D = x+H_1$, $s_L = 0$, $s_R = W$
It is guaranteed that the pictures don't overlap nor touch each other, and for all $i$ from $1$ to $N+K$, $0 \leq U_i < D_i \leq H_2$, $0 \leq L_i < R_i \leq W$.
Output
$Q$ lines, one for each change given in the input, with two integers answering the two questions present in the statement, in the order in which these questions were asked.
4 4 2 5 5
1 2 0 1
1 3 2 3
0 3 4 5
4 5 2 4
M 3
A 5 3 4 0 1
M 2
D 5
1 3
1 0
2 1
0 1
Note
The five images in the statement reflect the initial configuration of the example and the configuration after each of the changes, in order. Note that the blue rectangle in each image represents the subrectangle of the panel visible on the screen, while the gray rectangles correspond to the pictures.
The ids of the pictures visible in each of these five moments are: $[1,2,3]$, $[4]$, $[4,5]$, $[2,3,5]$ and $ [2,3]$