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]，q[i]≤10^6)**。

Samples

3 3
BBR
R 1
B 2
B 1

3
2
1

4 2
BRRB
B 1
R 3

1
-1

Hint

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