P8327 [COCI 2021/2022 #5] Radio

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`.

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.

For each `C` operation, output `DA` or `NE`.

**[Sample 1 Explanation]** |Index of `C` Operation|Turned-on Stations|Interference?| | :----------: | :----------: | :----------: | |$1$|$1,2,3$|No| |$2$|$1,2,3,6$|Yes| |$3$|$1,3,6$|Yes| **[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](https://hsin.hr/coci/contest5_tasks.pdf) Task 4 Radio. Translated by ChatGPT 5