Radio

문제

In Croatia there are $nn$ radio stations. Each station has a concession on one of $nn$ frequencies denoted by positive integers from $11$ to $nn$. The frequencies were not chosen ideally so sometimes noise appears when multiple stations are broadcasting at the same time. To be more precise, if two radio stations, with frequencies $aa$ and $bb$ respectively, are broadcasting at the same time, noise will appear if $aa$ and $bb$ are not relatively prime. The listeners, of course, do not like the noise, so when they hear it they switch to another station.

To solve this noise problem, the radio station owners are asking you to write a program which simulates the actions of the radio stations. Your program needs to support two types of queries:

1. $SS$ $xx$: If not currently broadcasting, the station with frequency $xx$ starts broadcasting, and if it is already broadcasting, it stops.
2. $CC$ $ll$ $rr$: Check if there exists a pair of broadcasting stations whose frequencies $aa$ and $bb$ are from the interval $[l,r][l,\; r]$ and such that $\gcd (a,b)\mathrm{\ne }1\backslash gcd\{(a,\; b)\}\; \backslash ne\; 1$. If such a pair exists, print DA, otherwise print NE.

Initially, no station is broadcasting.

입력

The first line contains positive integers $nn$ and $qq$ (1 ≤ n ≤ 1\,000\,000, 1 ≤ q ≤ 200\,000), the number of radio stations (and frequencies), and the number of queries, respectively.

The $ii$-th of the next $qq$ lines contains a description of the $ii$-th query. For queries of the first type it will hold that 1 ≤ x ≤ n, and for queries of the second type it will hold that 1 ≤ l ≤ r ≤ n.

출력

Print the answers to the queries of the second type in order, in separate lines.

힌트

Clarification of the first example:

The stations broadcasting during the first C type query are 1, 2 and 3. These numbers are all relatively prime to each other so they create no noise. Once station 6 begins to broadcast, it creates noise with stations 2 and 3. After station 2 stops broadcasting the noise with station 3 persists.

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