题目背景

题目描述

给定 $n,m$，你需要维护一个 $[1,n)$ 的数轴上区间的初始为空的可重集合，支持三种操作共 $m$ 次：

1. 插入一个区间 $[l,r)$。
2. 删除第 $t$ 次操作插入的区间。
3. 给出一个区间 $[l,r)$，判断当前可重集合中是否存在一个子集，使得子集中所有区间的并恰好是 $[l,r)$。

输入格式

第一行两个整数 $n,m$。

下面 $m$ 行，每行若干个整数描述一次操作，可能是 1 l r、2 t 或 3 l r。

输出格式

对于每个询问，输出一行一个大写字母 Y 或 N。Y 表示存在这样的子集，N 反之。

5 5
1 1 3
1 2 4
3 1 4
2 1
3 1 4

Y
N

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

N
N
Y
Y
N
N
N

提示

样例解释

对于样例 $1$，第一次询问时的可重集合为 $\{[1,3),[2,4)\}$，$[1,3)\cup [2,4)=[1,4)$。

第二次询问时的可重集合为 $\{[2,4)\}$，显然不存在满足条件的子集。

数据规模与约定

本题采用捆绑测试。

$\mathrm{Subtask}$	$n\le$	$m\le$	特殊性质	分数
$1$	$10^3$			$10$
$2$	$10^6$	$5\times 10^5$	$\text A$	$15$
$3$			$\text B$	$30$
$4$	$2\times 10^5$			$10$
$5$	$10^6$	$5\times 10^5$		$35$

特殊性质 $\text A$：保证不存在 $2$ 操作，且所有 $1$ 操作在所有 $3$ 操作之前。

特殊性质 $\text B$：保证不存在 $2$ 操作。

对于所有数据，保证 $2\le n\le 10^6$，$1\le m\le 5\times 10^5$，$1\le l<r\le n$。

保证所有操作 $2$ 对应的 $t$ 都是此前的操作 $1$ 且所有 $t$ 互不相同。