다리

강을 사이에 두고 북쪽과 남쪽에 각각 $N$개의 마을이 있다. 북쪽 마을은 $1$부터 $N$, 남쪽은 $N+1$부터 $2N$까지 번호가 붙는다. 같은 강변에서 동쪽에 있는 마을일수록 번호가 크다.

북쪽 강변에는 각 마을(마을 $N$ 제외)에서 바로 동쪽 이웃으로 가는 일방통행 도로가 있다. 남쪽 강변에는 각 마을(마을 $N+1$ 제외)에서 바로 서쪽 이웃으로 가는 일방통행 도로가 있다.

도로는 안전상의 이유로 영구 폐쇄될 수 있다. 강을 가로지르는 다리는 반대편 두 마을을 양방향으로 연결하며, 한 번 지으면 무너지지 않는다. 다리는 서로 교차하지 않으며, 각 마을은 반대편과 최대 한 개의 다리로만 연결된다.

초기에는 모든 도로가 열려 있고 다리는 없다. 이후 $M$개의 사건이 시간 순으로 주어진다.

• A G1 G2: 마을 $G1$과 $G2$ 사이에 다리를 건설한다.
• B G1 G2: 마을 $G1$과 $G2$ 사이의 일방통행 도로를 폐쇄한다.
• Q G1 G2: 현재 도로와 다리만으로 $G1$에서 $G2$로 갈 수 있는지 묻는다.

첫 줄에 $N$ ($1 \le N \le 10^9$)과 $M$ ($1 \le M \le 200\,000$)이 주어진다.

다음 $M$줄에 사건이 주어진다. 각 사건의 마을 번호 $G1$, $G2$는 $1 \le G1, G2 \le 2N$이며 서로 다르다. 폐쇄되는 도로는 그 시점까지 통행 가능했고, 건설되는 다리는 그 시점까지 존재하지 않았다.

각 Q 사건에 대해, $G1$에서 $G2$로 갈 수 있으면 DA, 없으면 NE를 입력 순서대로 한 줄에 하나씩 출력한다.