Description

历史学家dhh正在研究一个奇怪的王国的历史。当前阶段的任务是研究该国的交通。

根据这个奇怪的王国的史书记载，史书开始记载前这个王国有 $n$ 个城市(城市从 $0$ 开始标号)，但所有城市之间都没有道路相连。

每一年，在位的国王会修建一条双向道路 $x\rightarrow y$，一条道路可能被修建多次。而在这之间，国王会计划进行若干次旅行。对于计划进行的一次旅行 $st\rightarrow ed$，如果当时能完成这次旅行，而 $t$ 年前不能完成这次旅行，那么国王会对之前的建设成果感到满意，否则他会很生气，并在他感到满意之前（包括使他满意的那次旅行）都让史官记录下错误的信息，怎么样得到正确信息将在输入格式中描述。

当然在这些年中也发生了若干次国王的交替，而每个国王的c值不一定相同，但在国王在位期间c值不会改变（初始国王的 $c$ 值为 $0$，其他的 $c$ 值可通过记载得到），新上位的国王开始处于不生气的状态。

请根据史书帮助dhh得出国王每次对于计划旅行是否满意，从而使dhh能够研究该国的交通。

Input Format

多组数据，到EOF结束。

每组数据第一行两个整数 $n,m$，表示初始城市数和史书记载的内容数。

接下来m行，每行是以下三种格式之一：

K v表示国王交替，如果被替换的国王是生气的（即这个是错误信息），那么新国王的 $c$ 值为 $v+$被替换的国王的c值，否则新国王的 $c$ 值为 $v$。

R x y，表示史书上记载的是国王修建了 $x\rightarrow y$ 的双向道路，如果这是错误信息，那么真实信息为修建 $(x+c) \bmod n\rightarrow (y+c) \bmod n$ 的道路，否则为修建 $x \bmod n\rightarrow y \bmod n$ 的道路。

T st ed t，表示国王计划进行的一次 $st\rightarrow ed$ 的旅行，且比较的是 $t$ 年前的情况（国王可能会和史书开始记载以前的情况比较），如果这是错误信息，那么真实信息为国王计划进行的一次 $(st+c) \bmod n\rightarrow (ed+c) \bmod n$ 的旅行，且比较的是 $(t+c) \bmod n$ 年前的情况，否则为一次 $st \bmod n\rightarrow ed \bmod n$ 的旅行，且比较的是 $t \bmod n$ 年前的情况。

注意只有遇到R操作才会使年份的记数 $+1$。

Output Format

每组数据对于每个T的记录输出一行，如果此次旅行计划令国王满意，则输出Y，否则输出N。

Sample

样例输入

3 7 
R 0 1
T 0 1 1 
K 1 
R 0 1 
T 0 1 1
R 0 1
T 1 2 0

样例输出

Y
N
Y

Hint

对于 $30\%$ 的数据，满足 $1\le N\le 1000，1\le M\le 10000$；

对于 $100\%$ 的数据，满足 $1\le N,M\le 3\times 10^5，0\le v,x,y,st,ed<N，0\le t\le m$。数据组数 $\le 10$。