Ở đất nước X có ~n~ đài phát thanh được ký hiệu bằng các số nguyên dương từ 1 đến n. Nếu hai đài phát thanh, với tần số tương ứng là a và b, phát sóng cùng lúc, sẽ bị nhiễu nếu a và b không nguyên tố cùng nhau. Để giải quyết vấn đề nhiễu này, các đài phát thanh yêu cầu bạn viết một chương trình hỗ trợ hai loại truy vấn:

Loại ~1~ có dạng S x: Nếu đài có tần số x chưa phát sóng thì bắt đầu phát sóng, và nếu đang phát sóng thì dừng.

Loại ~2~ có dạng C l r: Kiểm tra xem có tồn tại một cặp đài phát sóng có tần số a và b nằm trong đoạn ~[l, r]~ mà ~gcd(a, b) \neq 1~ hay không. Nếu tồn tại một cặp như vậy, thì in ra DA, nếu không thì in ra NE.

Ban đầu, không có đài nào đang phát sóng.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ và ~q~ ~(1 \leq n \leq 1 000 000, 1 \leq q \leq 200 000)~, tương ứng là số đài phát thanh và số truy vấn.

Trong ~q~ dòng tiếp theo, mỗi dòng chứa một truy vấn. Nếu là truy vấn loại ~1~ thì luôn đảm bảo ~(1 \leq x \leq n)~, nếu là truy vấn loại ~2~ thì đảm bảo ~(1 \leq l \leq r \leq n)~.

Output

Trên từng dòng, mỗi dòng in ra kết quả truy vấn loại ~2~ .

input

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

output

DA
NE
DA