Islands

For your summer vacation, you've decided to visit N Greek islands. Throughout the year, you planned the details of your trip: which islands to visit, in what order, what landmarks to see...

As you haven't yet decided how long you want to stay on each island, you purchase N-1 open tickets from the "Cheap Unreliable Lines" company, one for each pair of consecutive islands you want to visit. So, for each island i, you can travel to island i+1 whenever you want. We assume the islands are numbered from 1 to N.

However, you forgot what the wise folks say: "When man makes plans, God laughs." The "Cheap Unreliable Lines" company announces strikes. As a result, you are forced to make changes to your trip. Nevertheless, you insist on the order in which you want to visit the islands. Specifically, the "Cheap Unreliable Lines" can interrupt routes between some islands at any time. Similarly, if the company's workers' demands are met, it can announce the resumption of routes at any time.

If you find yourself on island i and want to move to the next island i+1, but this route has been interrupted due to strikes, you can pay for a new ticket from another company, the "Expensive Reliable Lines." Conversely, if this route has not been interrupted, you can move between the two islands without paying, using your initial open tickets.

Since the company's announcements will happen while you are already traveling, you want to be able to quickly answer questions like: Based on the current information, if I am on island i and have enough money for k new tickets, what is the farthest island I can reach?

Problem

Develop a program in one of the Pascal, C, C++, Java languages that will help you plan your trip. Your program will read the announcements from the "Cheap Unreliable Lines" and your own questions. For each question, it will print the farthest island you can reach based on the constraints.

Input

The input file named islands.in is a text file with the following structure. The first line contains two integers, separated by a space: the number of islands N and the number Q of announcements/questions in chronological order. Then follow the descriptions of the Q announcements/questions.

Specifically, each line contains a character T, and two integers a and b.

If the character is the letter "D," then the company announces that it ceases to operate routes between all pairs of islands (i, i+~1~), for every a ~\le~ i ~<~ b.

If the character is the letter "B," then the company announces that it operates routes between all pairs of islands (i, i+~1~), for every a ~\le~ i ~<~ b. Possibly, some of these routes were already in operation.

If the character is the letter "Q," then you ask the program what is the farthest island you can reach if you start from island a and have enough money for b tickets.

Output

The output file named islands.out is a text file with the following structure. It should contain one line for each question (i.e., the letter "Q"), in order. This line should contain an integer between ~1~ and N, the answer to the corresponding question.

Examples of Input - Output Files

STDIN (islands.in)

8 5
Q 3 0
D 3 6
Q 2 2
B 4 5
Q 2 2

STDOUT (islands.out)

8
5
8

Explanation: We have N=~8~ islands, and Q=~5~ announcements/questions.

First, we have the question: If I am on island a=~3~ and have money for b=~0~ tickets, where can I reach? The answer is ~8~ because no routes have been interrupted yet, so I can reach the last island.

Next is an announcement that routes are not operating from island ~3~ to ~6~, meaning between islands (~3~,~4~), (~4~,~5~), (~5~,~6~).

Then comes the question: If I am on island a=~2~ and have money for b=~2~ new tickets, where can I reach? The answer is ~5~ because I don't pay to go from ~2~ to ~3~, pay to go to ~4~, and then to ~5~. I can't continue because I would have to pay again to go to ~6~.

Following is an announcement that the route (~4~,~5~) is now operating. Therefore, the only routes not operating now are (~3~,~4~) and (~5~,~6~).

Next is the question: If I am on island a=~2~ and have money for b=~2~ tickets, where can I reach? Now the answer is ~8~. I don't pay to go from ~2~ to ~3~, pay to go to ~4~, don't pay to go to ~5~, pay to go to ~6~, and then don't pay to go to ~7~ and ~8~.

Constraints:

• ~1 \le N \le 500.000~ and ~1 \le Q \le 500.000~
• For each announcement (~a_i~,~b_i~), it will be ~1 \le a_i < b_i \le N~.
• For each question (~a_i~,~b_i~), it will be ~1 \le a_i \le N~ and ~0 \le b_i < N~.
• For test cases worth 10%, ~N, Q \le 1.000~.
• For test cases worth 20%, no announcement will be given after a question.
• For test cases worth 30%, each announcement (~a_i~,~b_i~) will have ~b_i=a_i+1~.

Attention! Make sure to read the input and print the output efficiently, especially if you are programming in C++ or Java.

Formatting: In the output, each line terminates with a newline character. Maximum execution time: ~1~ sec. Maximum available memory: ~256~ MB.