Bridges

A river runs east-west with $N$ towns on the north bank ($1$ to $N$) and $N$ on the south ($N+1$ to $2N$). On each bank, labels increase toward the east.

On the north bank, each town except $N$ has a one-way road to its eastern neighbor. On the south bank, each town except $N+1$ has a one-way road to its western neighbor.

Roads may be permanently closed. Bridges connect one north town to one south town, work in both directions, never break, never cross, and each town uses at most one bridge.

Initially all roads are open and no bridges exist. Process $M$ events in order:

• A G1 G2: build a bridge between $G1$ and $G2$.
• B G1 G2: close the one-way road between $G1$ and $G2$.
• Q G1 G2: ask whether $G1$ can reach $G2$ with current roads and bridges.

Line 1: $N$ ($1 \le N \le 10^9$) and $M$ ($1 \le M \le 200\,000$).

Next $M$ lines describe events. Town ids satisfy $1 \le G1, G2 \le 2N$ and differ. Closed roads were open before; built bridges did not exist before.

For each Q event, print DA if a route exists, otherwise NE, in input order.