Problem Description

There are $n$ radio stations in Croatia, all initially turned off. If two stations $i,j$ are turned on at the same time and $i,j$ are not coprime, then they will interfere with each other.

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

1. S x: Toggle the status of station $x$, i.e., turn it off if it is on, and turn it on if it is off.
2. C l r: Check whether there exists interference within $[l,r]$. If it exists, output DA; otherwise output NE.

Input Format

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

The next $q$ lines describe the operations. The exact input format is given in the statement description.

Output Format

For each C operation, output DA or 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

Hint

[Sample 1 Explanation]

[Constraints and Notes]

This problem uses bundled testdata.

• 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 testdata, $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.

Translated by ChatGPT 5