在克罗地亚有 $n$ 个广播电台。每个电台拥有 $1$ 到 $n$ 之间的一个频率使用权，频率用正整数表示。由于频率分配不够理想，当多个电台同时广播时，有时会出现噪音。更准确地说，如果两个频率分别为 $a$ 和 $b$ 的电台同时广播，当 $\gcd(a, b) \neq 1$ 时，就会产生噪音。听众当然不喜欢噪音，所以当他们听到噪音时，会切换到另一个电台。

为了解决这个问题，电台所有者请求你编写一个程序来模拟电台的运作。你的程序需要支持以下两种类型的查询：

1. S x：如果频率为 $x$ 的电台当前未在广播，则开始广播；如果它已经在广播，则停止广播。
2. C l r：检查是否存在一对正在广播的电台，其频率 $a$ 和 $b$ 均在区间 $[l, r]$ 内，且满足 $\gcd(a, b) \neq 1$。如果存在这样的一对电台，输出 DA，否则输出 NE。

初始时，没有任何电台在广播。

输入格式

第一行包含两个正整数 $n$ 和 $q$ ($1 \le n \le 1\,000\,000, 1 \le q \le 200\,000$)，分别表示广播电台（及频率）的数量和查询的数量。

接下来的 $q$ 行，每行描述一个查询。对于第一类查询，满足 $1 \le x \le n$；对于第二类查询，满足 $1 \le l \le r \le n$。

输出格式

按顺序输出第二类查询的结果，每行一个。

子任务

样例

输入 1

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

输出 1

NE
DA
DA

输入 2

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

输出 2

DA
NE
DA

输入 3

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

输出 3

DA
DA
NE

说明

第一个样例的解释： 在第一次 C 类型查询时，正在广播的电台频率为 $1, 2$ 和 $3$。这些数字两两互质，因此不会产生噪音。一旦 $6$ 号电台开始广播，它会与 $2$ 号和 $3$ 号电台产生噪音。在 $2$ 号电台停止广播后，与 $3$ 号电台之间的噪音依然存在。