Gats and the Fickle Yarn
Gats is jumping among scratching posts standing in a row. The posts are indexed from left to right, and post has height .
Gats holds a magic yarn ball that always points either left or right. One jump is performed as follows:
- If the ball points left, Gats jumps to the closest post with and .
If no such post exists in the pointed direction, that jump takes Gats outside the row and no later jumps are made. After every successful jump to a post, the yarn ball immediately changes direction.
For each query, Gats starts on post while the ball initially points in direction . Report where Gats is after up to jumps, stopping earlier if he leaves the row.
Input
The first line contains two integers and (), the number of posts and the number of queries. The second line contains integers (), the heights of the posts in order. The next lines contain the queries. The -th query line contains an integer , a character , and an integer (, , ). The character means the yarn ball initially points left, and means it initially points right. All tokens on a line are separated by spaces.
Output
Print lines. For the -th query, print a single integer. Print the index of the post occupied by Gats after the process for that query, or print if Gats has left the row. If , print .
Samples
Sample 1
Input
5 4 3 1 4 2 5 2 R 3 4 L 2 1 R 0 5 L 10
Output
0 5 1 0
In the first query, Gats goes from post to post , then leaves the row while trying to jump left, so the answer is . In the second query, Gats goes from post to post to post . In the third query, , so Gats remains on post . In the fourth query, Gats leaves the row on the first jump.