题目描述

译自 COCI 2021/2022 Contest #5 T4「Radio」

在克罗地亚有 $n$ 个电台，每一个电台有其专属的频率，频率的范围为 $1 \sim n$ 的整数。

电台有可能相互干扰，神秘的是，如果两个开启电台的频率 $x$, $y$ 不互质，那么他们就会相互干扰。

你需要写一个程序，支持如下操作：

• S x：将频率为 $x$ 的电台状态取反，也就是说，如果原本关闭，就开启，如果原本开启，就关闭。
• C l r：检查是否存在频率为 $x, y \in [l, r]$ 的开启的电台使得他们相互干扰，如果存在，输出 DA，否则输出 NE。

一开始没有电台是开启的。

---

输入格式

第一行两个整数 $n, q$，$n$ 的意义如题目描述，$q$ 表示操作个数。

接下来 $q$ 行，每行一个操作，具体输入格式见题目描述。

---

输出格式

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

---

样例 1

输入

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

输出

NE
DA
DA

• 第一次询问时，被开启的电台频率分为 $1, 2, 3$，不存在相互干扰。
• 第二次询问时，被开启的电台频率分为 $1, 2, 3, 6$，存在相互干扰。
• 第三次询问时，被开启的电台频率分为 $1, 3, 6$，存在相互干扰。

---

样例 2

输入

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

输出

DA
NE
DA

---

样例 3

输入

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

输出

DA
DA
NE

---

数据范围与提示

对于全部数据，$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$。

Subtask 编号	特殊限制	分值
1	$n \le 100$，$q \le 200$	10
2	对于全部 C 操作，满足 $l = 1$，$r = n$	30
3		70

---