實時陰影是電子游戲中最為重要的畫面效果之一。在計算機圖形學中，通常使用陰影映射方法來實現實時陰影。

游戲開發部正在開發一款 2D 游戲，同時希望能夠在 2D 游戲中模仿 3D 游戲的光影效果，請幫幫游戲開發部！

給定 x-y 平面上的 n 個矩形，矩形的邊界平行于坐標軸，且可能相互重疊。同時給定點光源的坐標。現有 m 次操作，每次操作添加或刪除一個矩形，或詢問 x 軸上的一點是否在陰影內。

輸入格式

第一行，兩個整數 $n,m$($1\le n,m\le 2\times 10^5$)。
第二行，兩個整數 $l_x,l_y$，表示光源的坐標為 $(l_x,l_y)$。$|l_x|\le 2\times 10^5,0<l_y\le 2\times 10^5$。
接下來 $n$ 行，每行 5 個整數 $id,x,y,w,h$，表示編號為 $id$ 的矩形，左下角坐標為 $(x,y)$，寬為 $w$，高為 $h$。
接下來 $m$ 行，每行先輸入一個正整數 $opt$∈[1,3]。

• 若 $opt=1$，則接下來輸入 5 個整數 $id,x,y,w,h$，表示增加一個編號為 $id$，且左下角坐標為 $(x,y)$，寬和高為 $w$ 和 $h$ 的矩形。
• 若 $opt=2$，則接下來輸入一個整數 $id$，表示刪除編號為 $id$ 的矩形。
• 若 $opt=3$，則接下來輸入一個整數 $p$，表示查詢坐標 $(p,0)$ 是否在陰影中。

$1\le id\le 4\times 10^5$
$|x|\le 2\times 10^5,0<y\le 2\times 10^5$
$0<w,h\le 2\times 10^5$
$|p|\le 10^9$
保證任意時刻場景中所有矩形的 $id$ 互不相同。保證所有矩形各個頂點的 $y$ 坐標一定嚴格小于光源的 $y$坐標。若詢問點在陰影的邊界上，仍算作在陰影內。

輸出格式

對于每個 $opt=3$ 的詢問，若詢問的點在陰影中，則輸出一行 YES，否則輸出一行 NO。

樣例

input

3 19
4 7
1 1 1 2 1
2 6 1 2 3
3 5 2 4 1
3 -1
3 0
3 2
3 3
3 4
3 5
3 6
3 12
3 13
3 14
1 4 4 5 2 1
3 3
3 4
3 5
3 18
3 19
2 1
3 2
3 3

output

NO
YES
YES
NO
NO
NO
YES
YES
YES
NO
NO
YES
YES
YES
NO
NO
NO

提示

在進行所有修改操作之前，所有矩形的位置如下 (綠色部分為陰影區域)：

在加入一個矩形后，所有矩形的位置如下：

在刪除一個矩形后，所有矩形的位置如下：

很容易想到利用線段樹維護陰影區間，添加陰影即為在[l,r]范圍內進行+1操作，刪除陰影為-1

但是本題的數據范圍過大，特別注意當光源與矩形非常接近時，光線幾乎平行于x軸，這時用long long都會存在爆精度問題

所以必須進行離散化

我們可以發現需要用到的坐標是有限的，最多不超過$2\times n+m$個坐標點，用到的坐標點為線段端點(l,r)和查詢位置p

AC代碼如下

注意這題的時間復雜度卡的很死，需要采用IO加速，同時切忌使用STL容器

#include <iostream>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
#define int long long
const int max_n = 5e5 + 50;
const int max_m = 5e5 + 50;
const int max_len = 1e6 + 50;
const double eps = 1e-8;typedef struct {int idx, x1, y1, x2, y2;
}node;typedef struct {int opt[6];
}query;typedef struct {double first, second;
}line;int n, m;
node arr[max_n];
query qarr[max_m];
int tmpidx, lineidx;
double tmparr[max_len];
line lines[max_n + max_m];
map<double, int>dict;
int tree[max_len];inline int read() {int x = 0, y = 1; char c = getchar();while (c < '0' || c > '9') {if (c == '-') y = -1;c = getchar();}while (c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}return x * y;
}inline int lowbit(int x) {return x & -x;
}int ask(int p) {int res = 0;for (int i = p; i > 0; i -= lowbit(i)) {res += tree[i];}return res;
}void add(int p, int x) {for (int i = p; i < max_len; i += lowbit(i)) {tree[i] += x;}
}double project(int x, int y) {if (x == arr[0].x1) return x;double k = double(y - arr[0].y1) / double(x - arr[0].x1);double b = k * x - y;return b / k;
}void process(node n) {double l, r, ret;l = r = project(n.x1, n.y1);ret = project(n.x1, n.y2);l = min(l, ret); r = max(r, ret);ret = project(n.x2, n.y1);l = min(l, ret); r = max(r, ret);ret = project(n.x2, n.y2);l = min(l, ret); r = max(r, ret);tmparr[tmpidx++] = l;tmparr[tmpidx++] = r;lines[lineidx++] = line{ l,r };
}inline bool equal(double x, double y) {return fabs(x - y) < eps;
}void discrete() {sort(tmparr, tmparr + tmpidx);int cnt = 0;for (int i = 0; i < tmpidx; i++) {if (i == 0) {dict[tmparr[i]] = ++cnt;continue;}if (tmparr[i] != tmparr[i - 1])dict[tmparr[i]] = ++cnt;}
}signed main() {n = read(); m = read();arr[0].x1 = read();arr[0].y1 = read();int tmpid;int cnt;tmpidx = lineidx = 0;for (cnt = 1; cnt <= n; cnt++) {tmpid = read();arr[tmpid].x1 = read();arr[tmpid].y1 = read();arr[tmpid].x2 = arr[tmpid].x1 + read();arr[tmpid].y2 = arr[tmpid].y1 + read();arr[tmpid].idx = cnt - 1;process(arr[tmpid]);}int optnum;for (int i = 1; i <= m; i++) {qarr[i].opt[0] = read();switch (qarr[i].opt[0]){case 1:tmpid = read();arr[tmpid].x1 = read();arr[tmpid].y1 = read();arr[tmpid].x2 = arr[tmpid].x1 + read();arr[tmpid].y2 = arr[tmpid].y1 + read();arr[tmpid].idx = cnt++ - 1;process(arr[tmpid]);qarr[i].opt[1] = tmpid;break;case 2:qarr[i].opt[1] = read();break;case 3:qarr[i].opt[1] = read();tmparr[tmpidx++] = qarr[i].opt[1];break;default:break;}}discrete();for (int i = 0; i < n; i++) {double l = lines[i].first;double r = lines[i].second;l = dict[l]; r = dict[r];add(l, 1);add(r + 1, -1);}for (int i = 1; i <= m; i++) {if (qarr[i].opt[0] == 1) {int p = qarr[i].opt[1];p = arr[p].idx;double l = lines[p].first;double r = lines[p].second;l = dict[l]; r = dict[r];add(l, 1);add(r + 1, -1);}else if (qarr[i].opt[0] == 2) {int p = qarr[i].opt[1];p = arr[p].idx;double l = lines[p].first;double r = lines[p].second;add(dict[l], -1);add(dict[r] + 1, 1);}else {double p = qarr[i].opt[1];if (ask(dict[p])) { printf("YES\n");}else printf("NO\n");}}return 0;
}