题目描述

克罗地亚有 $n$ 个初始状态下关闭的电台。当同时开启两个电台 $i,j$ 且 $i,j$ 不互质时，它们会互相干扰。

你需要写一个支持下列操作的程序：

1. S x：将电台的状态取反，即将原来开启的电台关闭，将原来关闭的开启。
2. C l r：检查在 $[l,r]$ 内是否存在互相干扰的现象。如果存在，输出 DA，否则输出 NE。

输入格式

第一行两个正整数 $n,q$，分别表示电台个数和操作次数。

接下来的 $q$ 行，具体输入格式见题目描述。

输出格式

对于每一次 C 操作，输出 DA 或者 NE。

6 8
S 1
S 2
S 3
C 1 6
S 6
C 1 6
S 2
C 1 6

NE
DA
DA

11 6
S 4
S 10
C 3 11
C 2 7
S 6
C 2 7

DA
NE
DA

20 7
S 10
S 15
S 3
C 10 15
S 10
C 3 15
C 3 10

DA
DA
NE

提示

【样例 1 解释】

【数据规模与约定】

本题采用捆绑测试。

• Subtask 1（10 pts）：$1 \le n \le 100$，$1 \le q \le 200$。
• Subtask 2（30 pts）：对于所有的 C 操作，$l=1,r=n$。
• Subtask 3（70 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le q \le 2 \times 10^5$，$1 \le x \le n$，$1 \le l \le r \le n$。

【来源】COCI 2021-2022#5 Task 4 Radio。