눈꽃 스키장에는 2개의 스키코스가 있다: 하나는 1번 지점에서 N번 지점까지 동쪽으로 가면서 순차적으로 내려가는 코스이고, 나머지 하나는 2N번 지점에서 N+1번 지점까지 서쪽으로 가면서 순차적으로 내려가는 코스이다. (그림 참조)

언제나처럼, 이번 겨울에도 스키장에 사람이 북적였는데, 그에 따라서 사고도 일어나기 시작했다. 사고가 난 곳은 수습을 해야 하기 때문에 길을 막아야 한다.

막힌 길이 많아짐에 따라 제대로 스키를 즐기지 못 하는 사람들이 늘어나면서, 스키장의 관리자인 세진이는 두 스키코스를 일직선으로 잇는 케이블카를 짓기 시작했다. 세진이는 합선을 방지하기 위해서 두 케이블카가 교차하거나 한 지점에 두 개 이상의 케이블카가 지나가지 않게 케이블카를 지을 것이다.

스키장에 오는 사람들은 각자만의 스키 계획을 가지고 있다. 각 사람들은 특정 지점에서부터 스키를 타기 시작해 특정 지점까지 간 후 스키타기를 마친다. 어떤 경우에는 그 계획이 불가능할 수도 있기 때문에 세진이가 사람들에게 계획이 가능한지 불가능한지 알려줘야 한다. 허나, 사람들이 너무 많고 스키장이 매우 크기 때문에 일일이 손으로 하는 것은 너무 힘들다.

세진이를 도와 각 사람들의 계획이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

입력 형식

• 첫 번째 줄에는 한 스키코스에 있는 지역의 수 N과 명령의 수 M이 주어진다. (1 ≤ N ≤ 10^9, 1 ≤ M ≤ 200,000)
• 두 번째 줄부터 M개의 줄에는 다음과 같은 형식으로 명령이 주어진다.
  • A G1 G2 : G1번 지점과 G2번 지점을 연결하는 케이블카를 짓는다. 두 지점은 서로 다른 스키코스 위에 있다.
  • B G1 G2 : G1번 지점과 G2번 지점 사이에서 사고가 나서 길을 막는다. 두 지점은 같은 스키코스 위에 있으며, 이웃한 위치에 있다.
  • Q G1 G2 : G1번 지점에서 G2번 지점으로 갈 수 있는 지 물어본다.
  처음에는 케이블카가 하나도 설치되어 있지 않으며, 막힌 길도 없다.

출력 형식

입력 예 1

5 6
A 4 9
Q 1 7
B 3 2
Q 1 7
A 1 8
Q 1 7

출력 예 1

DA
NE
DA
   
입력 예 2

6 10
A 3 7
A 4 10
Q 1 11
A 12 5
Q 2 11
B 10 11
Q 2 10
Q 9 6
B 1 2
Q 1 2

출력 예 2

NE
DA
DA
DA
NE

On the north bank, there is a one-way road from each town (except town N) to its nearest town to the east. On the south bank, there is a one-way road from each town (except town N + 1) to its nearest town to the west.

Given the fact there is a lot of heavy traffic, the roads can sometimes get run down so they are permanently blocked because of safety reasons. In order to enable connectivity of cities that are not necessarily on the same side of the bank, the people in charge build bridges that directly connect some two cities located on opposite sides of the river. Bridge construction is a financially challenging task so they are built with special attention and they can never be run down. Because of the same reason, the bridges are two-way, unlike cheap roads on the banks of the river.

Additionally, the constructed bridges will never intersect, not even in their starting or ending towns . thus, each town will be directly connected by a bridge with at most one town on the other side of the river.

Mirko works at the information office in a leading bus company. Every day hundreds of people come to him and ask whether it is possible to get from one town to another. Mirko then glances on roads that are currently passable and bridges built so far and checks if there is a way to get from one town to another. He likes this job very much, but it overlaps with his daily coffee break from 11 a.m. to 2 p.m. so he asked you to write a program that will do this job for him!

. Write a program that will simulate M events given in chronological order. Each event is either an information about a newly blocked road or an information about a newly built bridge or an enquiry from a traveler regarding the existence of a way between two towns. The events are given in the following form:

• ‘A G1 G2’ - a bridge is built between towns G1 and G2.
• ‘B G1 G2’ - a one-way road between towns G1 and G2 is blocked.
• ‘Q G1 G2’ - a traveler wants to know whether there is a way from town G1 to town G2, given

입력

• The first line of input contains integers N (1 <= N <= 10^9) and M (1 <= M <= 200 000), the number of towns on one bank of the river and the number of events.
• Each of the following M lines contains the description of a single event in the form described in the task. For town labels in the events, it will hold 1 <= G1,G2 <= 2N. The towns G1 and G2 will always be different.

출력

SCORING

입출력 예

input 

5 6
A 4 9
Q 1 7
B 3 2
Q 1 7
A 1 8
Q 1 7

output

DA
NE
DA

input

6 10
A 3 7
A 4 10
Q 1 11
A 12 5
Q 2 11
B 10 11
Q 2 10
Q 9 6
B 1 2
Q 1 2

output 

NE
DA
DA
DA
NE

출처:coci/2013-2014/contest7
번역:functionx