Given $n$ and $m$, you need to maintain a multiset of intervals on the number line $[1, n)$, initially empty. You must support $m$ operations of the following three types:

1. Insert an interval $[l, r)$.
2. Delete the interval inserted by the $t$-th operation.
3. Given an interval $[l, r)$, determine whether there exists a subset of the current multiset such that the union of all intervals in the subset is exactly $[l, r)$.

Input

The first line contains two integers $n$ and $m$.

The next $m$ lines each contain several integers describing an operation, which can be 1 l r, 2 t, or 3 l r.

Output

For each query, output a single uppercase letter Y or N on a new line. Y indicates that such a subset exists, and N indicates otherwise.

Examples

Input 1

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

Output 1

Y
N

Input 2

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

Output 2

N
N
Y
Y
N
N
N

Subtasks

Idea: critnos, Solution: critnos, Code: fjy666, Data: critnos

All data guarantees $2 \le n \le 10^6$, $1 \le m \le 5 \times 10^5$, and $1 \le l < r \le n$. For all operations of type 2, the index $t$ refers to a previous operation of type 1, and all such $t$ are distinct.