라디오

크로아티아에는 $n$개의 라디오 방송국이 있다. 각 방송국은 $1$부터 $n$까지의 양의 정수로 표시되는 $n$개의 주파수 중 하나를 사용할 권리를 가진다. 주파수가 이상적으로 정해지지 않아서, 여러 방송국이 동시에 방송하면 잡음이 생길 때가 있다. 정확히는, 주파수가 $a$와 $b$인 두 방송국이 동시에 방송할 때 $\gcd(a, b) \ne 1$이면 잡음이 생긴다. 청취자는 잡음을 싫어해서, 잡음이 들리면 다른 방송국으로 채널을 바꾼다.

이 문제를 해결하기 위해 방송국 운영자는 방송국의 동작을 시뮬레이션하는 프로그램을 요청했다. 프로그램은 두 가지 종류의 쿼리를 처리해야 한다.

1. S x: 주파수 $x$의 방송국이 방송 중이 아니면 방송을 시작한다. 이미 방송 중이면 방송을 멈춘다.
2. C l r: 방송 중인 방송국 가운데 주파수 $a$와 $b$가 모두 $[l, r]$에 속하고 $\gcd(a, b) \ne 1$을 만족하는 쌍이 있는지 확인한다. 있으면 DA, 없으면 NE를 출력한다.

처음에는 방송 중인 방송국이 하나도 없다.

첫 줄에는 양의 정수 $n$과 $q$가 주어진다 ($1 \le n \le 1\,000\,000$, $1 \le q \le 200\,000$). 각각 방송국의 수(주파수의 수)와 쿼리의 수이다.

이어지는 $q$개의 줄은 각각 하나의 쿼리를 나타낸다. 첫 번째 종류의 쿼리에서는 $1 \le x \le n$이고, 두 번째 종류의 쿼리에서는 $1 \le l \le r \le n$이다.

두 번째 종류의 쿼리에 대한 답을 입력 순서대로 한 줄에 하나씩 출력한다.

첫 번째 C 쿼리 시점에 방송 중인 방송국은 1, 2, 3이다. 이 수들은 서로소이므로 잡음이 생기지 않는다. 방송국 6이 방송을 시작하면 2, 3번 방송국과 잡음이 생긴다. 2번 방송국이 방송을 멈춘 뒤에도 3번 방송국과의 잡음은 계속된다.