Description

在S城有一段很诡异的马路，那段马路上的路灯要么红色的要么蓝色的，有一天，小潘突然想知道某一个位置的路灯是红色还是蓝色的，但是Ta不敢自己去

查，你可以编写一个程序帮帮Ta吗。小潘有m个询问，对于每个询问，Ta想知道某种颜色第 q[i] 次在什么地方出现。

Format

Input

第一行有两个正整数 n，m。（1 ≤ n, m ≤ 1000000）

第二行有n个字母(‘R’或’B’)，每个第 i 个字母马路上第 i 个路灯的颜色。

接下来 m 行，第i行有一个大写字母 a[i] (‘R’或’B’)和一个正整数 q[i] ，用空格隔开，表示查询颜色a[i] 第q[i] 次出现的位置。

Output

共 m 行,第i行一个整数,表示查询结果,若颜色a[i]出现次数少于 q[i] 次,则输出-1,否则输出颜色 a[i] 第 q[i ] 次出现的位置。( 0<a[i],b[i]<1000000)

Samples

3 3
BBR
R 1
B 2
B 1

3
2
1

4 2
BRRB
B 1
R 3

1
-1

Hint

数据量较大，注意使用更快的输入输出方式。