#2120 Problem G. DVDs

20  4 s   64 MB  

Description

DVD Rental shops are disappearing because of online video streaming. However, a very popular series has just been released and the shops are hoping that this series will boost their popularity. This series consists of $N$ DVDs (numbered from $0$ to $N-1$).

You own a rental shop and have a specific shelf for this series. There are $N$ slots in this shelf (numbered from $0$ to $N-1$ as well). When you first get this series, you place the DVD number i into the slot number i, obviously. A customer who is a fan of this series will want to rent a sequence of DVDs numbered $l$ to $r$. Knowing that you have a shelf for this series, the customer will just pick up all DVDs from slot $l$ to $r$, without checking the actual index of the DVDs. However, there is one crazy customer who comes into your shop just to swap two DVDs in the slots, i.e., this customer takes a DVD from the slot a and exchanges it with the DVD in the slot b. This causes lots of problems for normal customers since normal customer do not check the index of the DVDs. For no reason, this crazy customer comes to your shop quite often and you don't have enough time to chase him away.

Your task is to write a program that monitors the activities in this shop and indicates whether a renting customer actually get the DVDs she wants, i.e., the customer actually get the DVDs numbered l to r. Be noted that the DVDs may be in any order, we just want to know if the customer get the DVDs numbered $l$ to $r$. For example, let us assume that a customer comes to get DVDs from slot $2$ to $4$ and the slot $2$, $3$ and $4$ have DVDs numbered $4$, $2$, and $3$, respectively, we will say that the customer get what she wants.

For simplicity, we will assume that when a customer rents the DVDs, she will immediately watch all of it and place it back into the same slot they are taken. In other words, renting DVDs has no effect on the position of the DVDs at all.

Input

First line of input is a number of test cases $T ≤ 20$.

The first line of each test case contains two integer $N$ and $K$ $(1 ≤ N ≤ 100 000, 1 ≤ K ≤ 50 000)$ which gives the number of DVDs and the number of activities that happens in the shops, respectively. Following $K$ lines describes the activities in the shop in the order that they happen. Each line contains three integers $q$, $a$ and $b$  $q$ is either $0$, $1$ and $0 ≤ a ≤ b < N$. 

When $q$ is $0$, the activity is that a crazy customer comes in to swap DVDs in the slot number a and b. When $q$ is $1$, a renting activity happens. A normal customer who needs DVD numbered a to b comes in and get DVDs from slot $a$ to $b$. As noted earlier, this customer immediately uses the DVDs and returns it to the same slot (there is no change to the DVDs for this activity).

Output

For each renting activity, display a line with a word YES when the customer gets what she wants, i.e., when slot $a$ to $b$ have DVDs numbered $a$ to $b$, and display a word NO in any other case.

Sample Input

Sample Output

2
5 8
1 0 4
1 1 2
0 1 3
1 2 2
1 1 3
1 0 0
1 0 2
1 2 4
5 5
0 1 2
0 2 3
0 1 3
1 0 1
1 0 2
YES
YES
YES
YES
YES
NO
NO
YES
NO

Source

2013 ACM-ICPC Asia Thailand National On-site programming Contest