题目描述

小美的彩带是由一条长度为n的彩带一直无限循环得到的，彩带的每一个位置都有一个颜色，用ai表示。因此当i > n时，ai = ai - n 。

小美每次会从左往右或从右往左剪一段长度为x的彩带（每次剪掉就直接丢弃，下次剪切的起点是上次剪切的终点），她想知道她每次剪下来的彩带有多少种颜色。

输入描述

第一行输入两个整数n, q(1 <= n, q <= 2 * 10^5) 代表彩带长度、剪彩带次数。

第二行输入n个整数a1, a2, ... , an(1 <= ai <= 10^9) 代表彩带每一个位置的颜色。

此后q行，每行输入一个字符c和一个整数x(1 <= x <= 10^9; c ∈ {'L', 'R'}) 代表裁剪方向和裁剪长度，其中'L'说明从左往右剪，'R'说明从右往左剪 。

输出描述

对于每一次裁剪彩带，在一行上输出一个整数代表颜色数量。

输入示例

6 3
1 1 4 5 1 4
L 2
L 3
R 12

输出示例

1
3
3

提示信息

第一次剪彩带，剪下来的是 [1,1] ，有 {1} 这 1 种颜色；

第二次剪彩带，剪下来的是 [4,5,1] ，有 {1,4,5} 这 3 种颜色；

第三次剪彩带，剪下来的是 [1,1,4,5,1,4,1,1,4,5,1,4] ，有 {1,4,5} 这 3 种颜色。

时间限制：c/c++：1s；go：3s；其他语言：8s。