题目描述

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

小美每次会从左往后或从右往左剪一段长度为 $x$ 的彩带, 她想知道她每次剪下来的彩带有多少种颜色。

输入描述

第一行输入两个整数 $n, q\left(1 \leq n, q \leq 2 \times 10^{5}\right)$ 代表彩带长度、剪彩带次数。 第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1 \leq a_u \leq 1e9)$ 代表彩带每一个位置的颜色。

此后 $q$ 行, 每行输入一个字符 $c$ 和一个整数 $x$ 代表裁剪方向和裁剪长度, 其中 '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$ 颜色。