Radio Interference Detection

In Croatia, there are (n) radio stations, all initially turned off. When two stations (i) and (j) are turned on and (\gcd(i,j) > 1), they interfere with each other.

You are given a sequence of operations to perform on these radio stations. There are two types of operations:

1. S x: Flip the state of station (x). If it is off, turn it on; if it is on, turn it off.

2. C l r: Check if there exists at least one pair of turned on stations within the interval ([l,r]) that interfere with each other (i.e. for some (i, j) with (l \le i < j \le r), (\gcd(i,j) > 1)). Print DA if such a pair exists, otherwise print NE.

inputFormat

The first line contains two integers (n) and (q) representing the number of radio stations and the number of operations, respectively. Each of the following (q) lines contains an operation in one of the following formats:

S x - Flip the state of radio station (x).
C l r - Check the interval ([l, r]) for interfering radio stations.

outputFormat

For every operation of type C, output a single line containing either DA if interference is detected among the turned-on stations in the given interval, or NE otherwise.

sample

5 5
S 2
S 3
C 2 3
S 4
C 2 4

NE
DA