该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

抗日战争在华北平原地区广泛爆发。这里有n个村庄，所有的村庄都排成一条线。除了两端的两个村庄，每个村庄都与两个相邻的村庄直接连接。在这场战争中会发生许多事件，可以分为以下三种情况： D x：第x个村庄被摧毁，与此连接的道路也会被摧毁。 Q x：陆军司令部要求查询与第x个村庄直接或间接连接的村庄数量，包括其自身。 R：修复最后被摧毁的村庄，与其连接的道路会被修复。

Format

Input

输入的第一行包含两个正整数 n 和 m（n、m ≤ 50000），表示村庄和事件的数量。接下来的 m 行，每一行表示一个事件。

Output

对于每个查询Q x，输出与第x个村庄直接或间接连接的村庄数量，包括其自身。

Samples

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

1
0
2
4