[AdditionalFile3683.zip](file://AdditionalFile3683.zip?type=additional_file)

#3683. 「COCI 2022.3」Radio

标签: 传统 | 时间限制: 1500 ms | 内存限制: 512 MiB |

题目描述

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

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

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

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

1. S x：将频率为 $x$ 的电台状态取反，也就是说，如果原本关闭，就开启，如果原本开启，就关闭。
2. 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$。