Background

第一周的训练就结束了，可乐加冰和他的队友给大家出了点有趣的题，编程之路才刚刚开始，大家加油。！！！！在周赛千万不要爆0哦！！！！！！

Description

现在给你一个长度为n的有序的数组串，可乐加冰希望你能根据他的m条指令来进行相应的搜索查找，你能够帮他完成吗。如果可乐加冰说‘L’和一个数字X，那么请你找出这列数组中第一次出现X他的数组下标，如果可乐加冰说‘R’和一个数字X，那么请你找出这列数组中最后一次出现这个X他的数组下标。如果没有这个数，请你输出‘-1’； ps：下标从0开始！！！！！！

Input

第一行输入一个n，m，n表示数组长度，m表示可乐加冰的指令条数； 第二行输入一个长度为n的； 之后m行输入一个字符ch，和一个数字x表示要找的数

Output

输出m行，x被要求的下标或者“-1”

Samples

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

3
4
-1

Limitation

1s, 1024KiB for each test case.