H. Heaps of Queries
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The skew heap data structure can be represented as a root node storing an integer value, and pointers to its left and right children. Each child is either another node, or an empty heap. We work with a simplified version, as follows.

If we want to insert an integer $$$v$$$ into a heap $$$H$$$:

  • If $$$H$$$ is empty, then set $$$H$$$ to a new node storing the value $$$v$$$, and no left or right children.
  • Otherwise, swap the left and right children of the root. Then recursively insert $$$v$$$ into the left child of the root.

Farmer John loves inserting elements into skew heaps. Every afternoon, he starts with an empty skew heap $$$H$$$. For all $$$i = 1, 2, \ldots, n$$$ in sequence, he then inserts $$$i$$$ into $$$H$$$.

For example, here is a picture of the skew heap resulting from the insertions $$$1, 2, 3, 4, 5$$$:

Bessie, after watching this process, is curious about what the resulting heap will look like. She has $$$q$$$ queries. In each one, she gives you an integer $$$1 \leq x \leq n$$$, and a string $$$s$$$ consisting of characters L, R, and U, and needs you to answer the following question.

  • Suppose you start at the node labeled $$$x$$$, and for each $$$i = 1, 2, \ldots, |s|$$$ in sequence, go to the left child of the current node if $$$s_i = \texttt{L}$$$, go to the right child if $$$s_i = \texttt{R}$$$, and go to the parent if $$$s_i = \texttt{U}$$$. Tell Bessie the value stored in the node you end up at, or report that you go out of bounds of the heap during this process.
Input

The first line contains $$$q$$$, the number of Bessie's queries $$$(1 \leq q \leq 10^3)$$$.

The only line of each query contains $$$n$$$, $$$x$$$, and $$$s$$$ ($$$1 \leq x \leq n \leq 10^{9}$$$, $$$1 \leq |s| \leq 100$$$).

It is guaranteed that each $$$s$$$ consists of characters L, R, and U.

Output

For each query, output -1 if you reach an empty heap, or the value stored in the ending node otherwise.

Example
Input
14
5 1 L
5 1 R
5 1 LL
5 1 RL
5 1 LLL
5 1 U
5 4 UU
5 2 RLLLRLRRLLLLLLLRRRR
5 1 UL
5 5 LU
1 1 L
1 1 U
1 1 R
696969 69 LRUURLLLRU
Output
3
2
5
4
-1
-1
1
-1
-1
-1
-1
-1
-1
1605
Note

The first nine queries all have $$$n=5$$$. Refer to the picture above.

We can see that taking paths L, R, LL, and RL from the root lead us to nodes $$$3$$$, $$$2$$$, $$$5$$$, and $$$4$$$ respectively. Taking the paths RR or U, though, will lead us outside of the heap, so we output -1.

Note that taking the path UU from node $$$4$$$ will lead us $$$4 \rightarrow 2 \rightarrow 1$$$, so we output 1.

In the ninth query, we go outside the heap after the first U, so we output -1.