Problem Description

Croatia has $n$ radio stations that are initially turned off. When two stations $i$ and $j$ are turned on simultaneously and $i$ and $j$ are not coprime, they interfere with each other.

You need to write a program that supports the following operations:

1. S x: Toggle the state of the radio station, turning it on if it was off, and off if it was on.
2. C l r: Check if there is any interference within the range $[l, r]$. If there is, output DA, otherwise output NE.

Input Format

The first line contains two positive integers $n$ and $q$, representing the number of radio stations and the number of operations, respectively.

The next $q$ lines contain the operations as described in the problem statement.

Output Format

For each C operation, output DA if there is interference, or NE if there is no interference.

Sample Input and Output

Input Sample #1

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

Output Sample #1

NE
DA
DA

Input Sample #2

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

Output Sample #2

DA
NE
DA

Input Sample #3

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

Output Sample #3

DA
DA
NE

Notes

[Sample 1 Explanation]

[Data Range and Constraints]

This problem is grouped by subtasks.

• Subtask 1 (10 pts): $1 \le n \le 100$, $1 \le q \le 200$.
• Subtask 2 (30 pts): For all C operations, $l = 1, r = n$.
• Subtask 3 (70 pts): No additional constraints.

For $100\%$ of the data, $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$.

[Source] COCI 2021-2022#5 Task 4 Radio.

见题面 Input 部分

见题面 Output 部分