Grasshopper Jumps

N grasshoppers are waiting in a line to watch a show. While waiting, they get bored and perform one of the following moves:

• The grasshopper currently at position A jumps over B grasshoppers to its left.
• The grasshopper currently at position A jumps over B grasshoppers to its right.

The grasshoppers may have different heights. When a grasshopper jumps over others, it must jump high enough not to hit any of them with its legs. More precisely, the required jump height is the height of the tallest grasshopper it jumps over.

Given the sequence of jumps, output the required height for each jump in order.

The first line contains two integers N and J, the number of grasshoppers in the line and the number of jumps. (2 <= N <= 100000, 1 <= J <= 100000)

The second line contains N integers in the initial order, the heights of the grasshoppers. Each height is less than 100000. Initially, the first grasshopper is at position 1, the second at position 2, and so on.

Each of the next J lines describes one jump, in order. Each line contains an integer A, a direction character, and an integer B. A is the current position of the jumping grasshopper, with 1 <= A <= N. The direction is 'L' for left or 'D' for right. B is the number of grasshoppers it jumps over, with 1 <= B <= N.

Every jump is valid: B is at most the number of grasshoppers on the chosen side of the jumping grasshopper.

Print J lines. The i-th line must contain the required height of the i-th jump.

In the first jump, the grasshopper jumps over grasshoppers of heights 8, 4, and 9, so the required height is 9. In the second jump, it jumps over heights 3 and 7. In the final jump, it jumps over heights 3 and 4.