In Croatia there are ~n~ radio stations. Each station has a concession on one of ~n~ frequencies denoted by positive integers from ~1~ to ~n~. 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 ~a~ and ~b~ respectively, are broadcasting at the same time, noise will appear if ~a~ and ~b~ 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. S x: If not currently broadcasting, the station with frequency ~x~ starts broadcasting, and if it is already broadcasting, it stops.

2. C l r: Check if there exists a pair of broadcasting stations whose frequencies ~a~ and ~b~ are from the interval ~[l, r]~ and such that ~\gcd(a, b) \ne 1~. If such a pair exists, print DA, otherwise print NE.

Initially, no station is broadcasting.

Input Specification

The first line contains positive integers ~n~ and ~q~, the number of radio stations (and frequencies), and the number of queries, respectively.

The ~i^\text{th}~ of the next ~q~ lines contains a description of the ~i^\text{th}~ query. For queries of the first type it will hold that ~1 \le x \le n~, and for queries of the second type it will hold that ~1 \le l \le r \le n~.

Output Specification

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

Constraints

Subtask	Points	Constraints
~1~	~10~	~1 \le n \le 100~, ~1 \le q \le 200~
~2~	~30~	For all queries of the second type it holds that ~l = 1~ and ~r = n~.
~3~	~70~	~1 \le n \le 10^6~, ~1 \le q \le 2 \times 10^5~

Sample Input 1

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

Sample Output 1

NE
DA
DA

Explanation for Sample Output 1

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.

Sample Input 2

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

Sample Output 2

DA
NE
DA

Sample Input 3

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

Sample Output 3

DA
DA
NE