Задача №114942. Горилла и радиоприемник
Однажды огромный самец гориллы нашел в джунглях старый радиоприемник. Этот радиоприемник способен ловить сигнал с \(n\) радиостанций, с номерами \(1, 2, \ldots, n\). Изначально все радиостанции выключены .
Вам предстоит ответить на \(q\) запросов:
- Станция \(x\) включилась, если была выключена, и выключилась, в противном случае;
- Горилле интересно, образуют ли станции с номерами от \(l\) до \(r\) помехи .
Станции с номерами от \(l\) до \(r\) образуют помехи , если существуют включенные станции \(\langle a, b \rangle\), такие что \(l \le a < b \le r\) и \(gcd(a, b) \neq 1\).
В первой строке даны целые числа \(n\), \(q\) (\(1 \le n \le 10^6\), \(1 \le q \le 2 \cdot 10^5\)) — количества частот и запросов.
В следующих \(q\) строках описаны запросы.
Запрос первого типа описывается строкой S \(x\) (\(1 \le x \le n\)).
Запрос второго типа описывается строкой C \(l\) \(r\) (\(1 \le l \le r \le n\)).
Для каждого запроса второго типа выведите YES или NO . Вы можете выводить ответ в любом регистре.
Группа \(0\): тесты из условия — \(0\) баллов.
Группа \(1\): \(n \le 100\), \(q \le 200\) — \(9\) баллов.
Группа \(2\): \(l = 1\), \(r = n\) — \(13\) баллов.
Группа \(3\): радиостанции не выключаются — \(22\) балла.
Группа \(4\): без доп. ограничений — \(56\) баллов.
6 8 S 1 S 2 S 3 C 1 6 S 6 C 1 6 S 2 C 1 6
NO YES YES
11 6 S 4 S 10 C 3 11 C 2 7 S 6 C 2 7
YES NO YES
20 7 S 10 S 15 S 3 C 10 15 S 10 C 3 15 C 3 10
YES YES NO