T is a complete binary tree consisting of n vertices. It means that exactly one vertex is a root, and each vertex is either a leaf (and doesn't have children) or an inner node (and has exactly two children). All leaves of a complete binary tree have the same depth (distance from the root). So n is a number such that n + 1 is a power of 2.

In the picture you can see a complete binary tree with n = 15. [Image] 

Vertices are numbered from 1 to n in a special recursive way: we recursively assign numbers to all vertices from the left subtree (if current vertex is not a leaf), then assign a number to the current vertex, and then recursively assign numbers to all vertices from the right subtree (if it exists). In the picture vertices are numbered exactly using this algorithm. It is clear that for each size of a complete binary tree exists exactly one way to give numbers to all vertices. This way of numbering is called symmetric.

You have to write a program that for given n answers q queries to the tree.

Each query consists of an integer number u_{i} (1 ≤ u_{i} ≤ n) and a string s_{i}, where u_{i} is the number of vertex, and s_{i} represents the path starting from this vertex. String s_{i} doesn't contain any characters other than 'L', 'R' and 'U', which mean traverse to the left child, to the right child and to the parent, respectively. Characters from s_{i} have to be processed from left to right, considering that u_{i} is the vertex where the path starts. If it's impossible to process a character (for example, to go to the left child of a leaf), then you have to skip it. The answer is the number of vertex where the path represented by s_{i} ends.

For example, if u_{i} = 4 and s_{i} = «UURL», then the answer is 10.


-----Input-----

The first line contains two integer numbers n and q (1 ≤ n ≤ 10^18, q ≥ 1). n is such that n + 1 is a power of 2.

The next 2q lines represent queries; each query consists of two consecutive lines. The first of these two lines contains u_{i} (1 ≤ u_{i} ≤ n), the second contains non-empty string s_{i}. s_{i} doesn't contain any characters other than 'L', 'R' and 'U'.

It is guaranteed that the sum of lengths of s_{i} (for each i such that 1 ≤ i ≤ q) doesn't exceed 10^5.


-----Output-----

Print q numbers, i-th number must be the answer to the i-th query.


-----Example-----
Input
15 2
4
UURL
8
LRLLLLLLLL

Output
10
5

Difficulty: interview

Starter code:

Solutions:
def mask(n):
  if not n: return 0;
  m = 1
  while not (m & n):
    m *= 2
  return m
  
n, T = list(map(int, input().split()))
for t in range(T):
  cur = int(input())
  for ch in input():
    m = mask(cur)
    #print(ch, ":", m, cur, "->", end = " ")
    if ch == "U":
      next = (cur - m) | (m * 2)
      if next < n: cur = next
    elif ch == "L" and m > 1:
      cur -= m//2
    elif ch == "R" and m > 1:
      cur += m//2
    #print(cur)
  print(cur)  


n, q = [int(i) for i in input().split()]

def identify_row(x):
	for i in range(1, 64):
		power = 1 << i
		if x % power == power >> 1:
			return i

def some(x):
	r = identify_row(x)
	return x - (1 << (r - 1)) + 1

def left(x):
	r = identify_row(x)
	if r == 1: return x
	return x - (1 << (r - 2))

def right(x):
	r = identify_row(x)
	if r == 1: return x
	return x + (1 << (r - 2))

def parent(x):
	if x == (n + 1) >> 1:
		return x
	r = identify_row(x)
	return x + (1<<(r-1) if some(x) % (1 << (r + 1)) == 1 else -1<<(r-1))

for _ in range(q):
	t = int(input())
	c = input()
	for i in c:
		if i == 'U': t = parent(t)
		elif i == 'R': t = right(t)
		elif i == 'L': t = left(t)
		else: print('error', i)
	print(t)

import math

n, q = map(int, input().split())
maxh = int(math.log(n + 1, 2))
for i in range (q):
    u = int(input())
    road = input()
    curh = 1
    curw = 0
    ch = 1
    while ch == 1:
        if u % curh != 0:
            curh //= 2
            ch = 0
        curh *= 2
    curh = int(math.log(curh, 2))
    a = 1 << (curh - 1)
    b = 1 << curh
    curw = (u - a) // b + 1
    for move in road:
        if move == "L":
            if curh != 1:
                curh -= 1
                curw = curw * 2 - 1
                u -= 1 << (curh - 1)
        elif move == "R":
            if curh != 1:
                curh -= 1
                curw *= 2
                u += 1 << (curh - 1)
        else:
            if curh != maxh:
                if curw % 2 == 1:
                    u = (u + u + (1 << curh)) // 2
                    curh += 1
                    curw = curw // 2 + 1
                else:
                    u = (u + u - (1 << curh)) // 2
                    curh += 1
                    curw = curw // 2
    print(u)

import math

n, q = map(int, input().split())
maxh = int(math.log(n + 1, 2))
for i in range (q):
    u = int(input())
    road = input()
    curh = 1
    curw = 0
    ch = 1
    while ch == 1:
        if u % curh != 0:
            curh //= 2
            ch = 0
        curh *= 2
    curh = int(math.log(curh, 2))
    a = 1 << (curh - 1)
    b = 1 << curh
    curw = (u - a) // b + 1
    for move in road:
        if move == "L":
            if curh != 1:
                curh -= 1
                curw = curw * 2 - 1
                u -= 1 << (curh - 1)
        elif move == "R":
            if curh != 1:
                curh -= 1
                curw *= 2
                u += 1 << (curh - 1)
        else:
            if curh != maxh:
                if curw % 2 == 1:
                    u = (u + u + (1 << curh)) // 2
                    curh += 1
                    curw = curw // 2 + 1
                else:
                    u = (u + u - (1 << curh)) // 2
                    curh += 1
                    curw = curw // 2
    print(u)

from math import log
n, q = [int(i) for i in input().split()]
maxlvl = int(log(n + 1, 2)) + 1
steps = [2 ** i for i in range(maxlvl)]

def calc_lvl(m):
    for lvl in range(1, maxlvl):
        if (m - steps[lvl-1]) % steps[lvl] == 0:
            return (lvl, ((m - steps[lvl-1]) % (2 * steps[lvl]) == 0))

#print(calc_lvl(1))
#print(calc_lvl(3))
#print(calc_lvl(5))
#print(calc_lvl(7))
#print(calc_lvl(9))
#print(calc_lvl(11))
#print(calc_lvl(13))
#print(calc_lvl(15))


             
for i in range(q):
    strt = int(input())
    qwery = input()
    lvl, ind = calc_lvl(strt)
    
    for c in qwery:
        if c == 'U':  
            if strt == steps[-2]:
                continue
            if not ind:
                strt -= steps[lvl - 1]
                lvl, ind = calc_lvl(strt)
            else:
                strt += steps[lvl - 1]
                lvl, ind = calc_lvl(strt)
                
        elif c == 'L':
            if strt % 2 != 0:
                continue
            strt -= steps[lvl - 2]
            lvl, ind = lvl - 1, 1
            
        else:
            if strt % 2 != 0:
                continue
            strt += steps[lvl - 2]
            lvl, ind = lvl - 1, 0
            
    print(strt)
            
                
                

            


from math import log
n, q = [int(i) for i in input().split()]
maxlvl = int(log(n + 1, 2)) + 1
pows = [2 ** i for i in range(maxlvl)]

def calc_lvl(m):
    for lvl in range(1, maxlvl):
        if (m - pows[lvl-1]) % pows[lvl] == 0:
            return (lvl, ((m - pows[lvl-1]) % (2 * pows[lvl]) == 0))

for i in range(q):
    start = int(input())
    query = input()
    lvl, ind = calc_lvl(start)
    
    for c in query:
        if c == 'U':  
            if start == pows[-2]:
                continue
            start += (1 if ind else -1) * pows[lvl - 1]
            lvl, ind = calc_lvl(start)    
        else:
            if start % 2 != 0:
                continue
            start += (1 if c == 'R' else -1) * pows[lvl - 2]
            lvl, ind = lvl - 1, int((c == 'L'))
            
    print(start)
            
                
                

            


from math import log
n, q = [int(i) for i in input().split()]
maxlvl = int(log(n + 1, 2)) + 1
pows = [2 ** i for i in range(maxlvl)]
done = dict()

def calc_lvl(m):
    for lvl in range(1, maxlvl):
        if (m - pows[lvl-1]) % pows[lvl] == 0:
            return (lvl, ((m - pows[lvl-1]) % (2 * pows[lvl]) == 0))

for i in range(q):
    start = int(input())
    query = input()
    lvl, ind = calc_lvl(start)
    
    for c in query:
        if c == 'U':  
            if start == pows[-2]:
                continue
            start += (1 if ind else -1) * pows[lvl - 1]
            if start not in list(done.keys()):
                lvl, ind = calc_lvl(start)
                done[start] = (lvl, ind)
            else:
                (lvl, ind) = done[start]
        else:
            if start % 2 != 0:
                continue
            start += (1 if c == 'R' else -1) * pows[lvl - 2]
            lvl, ind = lvl - 1, int((c == 'L'))
            
    print(start)
            
                
                

            


from math import log
n, q = [int(i) for i in input().split()]
maxlvl = int(log(n + 1, 2)) + 1
pows = [2 ** i for i in range(maxlvl)]

def calc_lvl(m):
    for lvl in range(1, maxlvl):
        if (m - pows[lvl-1]) % pows[lvl] == 0:
            return (lvl, ((m - pows[lvl-1]) % (2 * pows[lvl]) == 0))

for i in range(q):
    start = int(input())
    query = input()
    lvl, ind = calc_lvl(start)
    
    for c in query:
        if c == 'U':  
            if start == pows[-2]:
                continue
            start += (1 if ind else -1) * pows[lvl - 1]
            lvl, ind = calc_lvl(start)    
        else:
            if start % 2 != 0:
                continue
            start += (1 if c == 'R' else -1) * pows[lvl - 2]
            lvl, ind = lvl - 1, int((c == 'L'))
            
    print(start)
            
                

            


import sys
n,q = map(int, input().split())

def lev(x):
    num = (x) & (-x)
    l = 0
    while num > 0:
        num =( num >> 1)
        l+=1
    return l
def up(x):
    l = lev(x)
    # left child
    if  not (((1<<l) & x) > 0):
        return x + (1<<(l - 1))
    #right child
    return x - (1<<(l - 1))
def left(x):
    l = lev(x)
    if( l == 1):
        return  0
        
    # left child
    return x - (1<<(l - 1)) + (1<<(l -2))
def right(x):
    l = lev(x)
    if( l == 1):
        return  0
    # left child
    return x + (1<<(l -2))
def isValid(x):
    return  0<x <= n
for i in range(q):
    u = int(input())
    s = input()
    for a in s:
        if a == 'U':
            nu = up(u)
        elif a == 'R':
            nu = right(u)
        else:
            nu = left(u)
        if isValid(nu):
            u = nu
    print(u)

from math import log
n, q = [int(i) for i in input().split()]
maxlvl = int(log(n + 1, 2)) + 1
pows = [2 ** i for i in range(maxlvl)]

def calc_lvl(m):
    for lvl in range(1, maxlvl):
        if (m - pows[lvl-1]) % pows[lvl] == 0:
            return (lvl, ((m - pows[lvl-1]) % (2 * pows[lvl]) == 0))

for i in range(q):
    start = int(input())
    query = input()
    lvl, ind = calc_lvl(start)
    
    for c in query:
        if c == 'U':  
            if start == pows[-2]:
                continue
            start += (1 if ind else -1) * pows[lvl - 1]
            lvl, ind = calc_lvl(start)    
        else:
            if start % 2 != 0:
                continue
            start += (1 if c == 'R' else -1) * pows[lvl - 2]
            lvl, ind = lvl - 1, int((c == 'L'))

            
    print(start)
            
                

            


import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,q = LI()
    nn = n
    k = 0
    while nn > 0:
        nn //= 2
        k += 1

    r = []
    ii = [2**i for i in range(k)]
    for _ in range(q):
        t = I()
        s = S()
        ti = 0
        for i in range(k):
            if ii[i] & t:
                ti = i
                break

        for c in s:
            if c == 'U':
                if ti == k-1:
                    continue
                if t & ii[ti]:
                    t ^= ii[ti]
                ti += 1
                t |= ii[ti]
                continue
            if ti == 0:
                continue
            if c == 'R':
                t |= ii[ti]
            else:
                if t & ii[ti]:
                    t ^= ii[ti]
            ti -= 1
            t |= ii[ti]
        r.append(t)

    return '\n'.join(map(str, r))


print(main())


import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,q = LI()
    nn = n
    k = 0
    while nn > 0:
        nn //= 2
        k += 1

    r = []
    ii = [2**i for i in range(k)]
    for _ in range(q):
        t = I()
        s = S()
        ti = 0
        for i in range(k):
            if ii[i] & t:
                ti = i
                break

        for c in s:
            if c == 'U':
                if ti == k-1:
                    continue
                if t & ii[ti]:
                    t ^= ii[ti]
                ti += 1
                t |= ii[ti]
                continue
            if ti == 0:
                continue
            if c == 'R':
                t |= ii[ti]
            else:
                if t & ii[ti]:
                    t ^= ii[ti]
            ti -= 1
            t |= ii[ti]
        r.append(t)

    return '\n'.join(map(str, r))


print(main())


def powersOfTwo():
    powers = {}
    powers[0] = 1
    for i in range(1, 70):
        powers[i] = powers[i - 1] * 2
    return powers

def log2(num):
    ans = 0
    while num > 1:
        num //= 2
        ans += 1
    return ans

def getlevel(num):
    count = 0
    while num % 2 == 0:
        num //= 2
        count += 1
    return count

def solve():
    n, q = list(map(int, input().rstrip().split()))
    powers = powersOfTwo()
    maxlevel = log2(n + 1) - 1
    for _ in range(q):
        num = int(input().rstrip())
        level = getlevel(num)
        string = input().rstrip()
        for char in string:
            assert 0 <= level <= maxlevel
            if char == 'U':
                if level < maxlevel:
                    a = num - powers[level]
                    b = num + powers[level]
                    if a == 0:
                        num = b
                    elif b > n:
                        num = a
                    elif getlevel(a) < getlevel(b):
                        num = a
                    else:
                        num = b
                    level += 1
            elif char == 'L':
                if level > 0:
                    num -= powers[level - 1]
                    level -= 1
            elif char == 'R':
                if level > 0:
                    num += powers[level - 1]
                    level -= 1
            else:
                raise ValueError
        print(num)

def __starting_point():
    solve()

__starting_point()

from math import *

n, q = list(map(int, input().split()))
depth = int(log2(n + 1))


def get_layer(u):
    for layer in range(depth):
        if u % (2 ** (layer + 1)) == 2 ** layer:
            return layer


def is_right_child(layer, u):
    return (u % 2 ** (layer + 1)) % 2 == 0


for x in range(q):
    u = int(input())
    layer = get_layer(u)
    steps = input()
    for s in steps:
        if s == 'U':
            if (layer == depth - 1):
                continue
            k = (u // (2 ** (layer + 1))) // 2
            layer += 1
            u = (2 ** (layer + 1)) * k + 2 ** layer
        elif layer == 0:
            continue
        elif s == 'R':
            k = (u // (2 ** (layer + 1))) * 2 + 1
            layer -= 1
            u = (2 ** (layer + 1)) * k + 2 ** layer
        elif s == 'L':
            k = (u // (2 ** (layer + 1))) * 2
            layer -= 1
            u = (2 ** (layer + 1)) * k + 2 ** layer
    print(u)


from math import *

n, q = list(map(int, input().split()))
depth = int(log2(n + 1))

def get_layer(u):
    for layer in range(depth):
        if u % (2 ** (layer + 1)) == 2 ** layer:
            return layer


for x in range(q):
    u = int(input())
    layer = get_layer(u)
    steps = input()
    for s in steps:
        if s == 'U':
            if (layer == depth - 1):
                continue
            k = (u // (2 ** (layer + 1))) // 2
            layer += 1
            u = (2 ** (layer + 1)) * k + 2 ** layer
        elif layer == 0:
            continue
        elif s == 'R':
            k = (u // (2 ** (layer + 1))) * 2 + 1
            layer -= 1
            u = (2 ** (layer + 1)) * k + 2 ** layer
        elif s == 'L':
            k = (u // (2 ** (layer + 1))) * 2
            layer -= 1
            u = (2 ** (layer + 1)) * k + 2 ** layer
    print(u)


def solve(n, m):
    h=m&-m
    for c in input():
        if c=='U' and m!=(n+1)>>1:
            m+= -h if (m+h)%(h<<2)==0 else h
            h<<=1
        if c in 'LR' and h>1:
            h>>=1
            m+= -h if c=='L' else h
    return m

n, m=map(int, input().split())
for _ in range(m):
    print(solve(n, int(input())))

def process_moves(v, moves, n):
    update = True
    for m in moves:
        if update:
            bit_pos = 0
            t = v
            while t > 0:
                if t & 1 == 1:
                    break
                t >>= 1
                bit_pos += 1

            power_of_2 = t == 1

        if m == 'U':
            if power_of_2:
                new_v = v << 1
            else:
                new_v = v & ~(1 << bit_pos) | (1 << (bit_pos + 1))
        elif m == 'L':
            if power_of_2:
                new_v = v >> 1
            else:
                if bit_pos > 0:
                    new_v = v & ~(1 << bit_pos) | (1 << (bit_pos - 1))
                else:
                    new_v = 0
        else:  # m == 'R'
            if bit_pos > 0:
                new_v = v | (1 << (bit_pos - 1))
            else:
                new_v = 0

        if 1 <= new_v <= n:
            update = True
            v = new_v

    return v


def main():
    n, q = list(map(int, input().split()))
    for i in range(q):
        s = int(input())
        moves = input()
        print(process_moves(s, moves, n))


def __starting_point():
    # import sys
    # sys.stdin = open("D.txt")
    main()

__starting_point()

def greatest_pow2_divisor(x):
    pow2 = 1
    while x % pow2 == 0:
        pow2 *= 2
    return pow2 // 2

def parent(x):
    pow2 = greatest_pow2_divisor(x)
    if ((x + pow2) // (pow2 * 2)) % 2 == 1:
    	return x + pow2
    return x - pow2

def left(x):
    if x % 2 == 1:
    	return x
    return x - greatest_pow2_divisor(x) // 2

def right(x):
    if (x % 2 == 1):
    	return x;
    return x + greatest_pow2_divisor(x) // 2;

numbers = list(map(int, input().split()))
n = numbers[0]
q = numbers[1]
root = (n + 1) / 2
for i in range(q):
	u = int(input())
	s = input()
	for c in s:
		if c == 'U':
			if u != root:
				u = parent(u)
		if (c == 'L'):
			u = left(u)
		if (c == 'R'):
			u = right(u)
	print(u)


n, m = map(int, input().split())
for i in range(m):
    k = int(input())
    d = k & -k
    for q in input():
        if q == 'U' and k != n + 1 >> 1:
            k += d if (k + d) % (d << 2) else -d
            d <<= 1
        if q in 'LR' and d > 1:
            d >>= 1
            k += d if q == 'R' else -d
    print(k)

#!/usr/bin/env python3

# solution after hunt:(

[n, q] = list(map(int, input().strip().split()))
bis = []
for i in range(q):
	u = int(input().strip())
	s = input().strip()
	bis.append((u, s))

d = len(bin(n)[2:])

def getk(u):
	b = bin(u)
	return len(b) - len(b.rstrip('0'))


def goLeft(u, k, d):
	if k == 0:
		return (u, k)
	else:
		return (u - 2**(k - 1), k - 1)

def goRight(u, k, d):
	if k == 0:
		return (u, k)
	else:
		return (u + 2**(k - 1), k - 1)

def goUp(u, k, d):
	if k == d - 1:
		return (u, k)
	elif getk(u + 2**k) == k + 1:
		return (u + 2**k, k + 1)
	else:
		return (u - 2**k, k + 1)

go = {'L': goLeft, 'R': goRight, 'U': goUp}

def process(u, s, d):
	k = getk(u)
	for c in s:
		(u, k) = go[c](u, k, d)
	return u

for u, s in bis:
	print(process(u, s, d))


def find(x):
    if root==x:
        u=root
    else:
        i=0
        s=2**i
        while x%s==0:
            i+=1
            s=2**i
        s=s//2
        y=i+1
        if (x-s)%(2**y)!=0:
            u=x-s
        else:
            u=x+s
    return u
n,q=list(map(int,input().split()))
root=(n+1)//2
for j in range(q):
    n1=int(input())
    str1=input()
    for j in range(len(str1)):
        up=find(n1)
        if str1[j]=='U':
            n1=(up)
        elif n1%2==0:
            if str1[j]=='L':
                if n1!=root:
                    n1=(n1-abs((up-n1)//2))
                else:
                    n1=(n1-n1//2)
            elif str1[j]=='R':
                if n1!=root:
                    n1=(n1+abs((up-n1)//2))
                elif n1%2==0:
                    n1=n1+n1//2
    print(n1)

n, q = list(map(int,input().split()))
par = n // 2 + 1
par = len(list(bin(par)[2:]))
for i in range(q):
    ui = int(input())
    si = input()
    temp = bin(ui)[2:]
    now = len(temp)
    num = list((par - now) * "0" + temp)
    now = par - now
    for i in range(len(num)):
        if str(num[i]) == '1':
            now = i
    for i in si:
        if i == "U":
            if now == 0:
                continue
            num[now] = 0
            now -= 1
            num[now] = 1
        elif i == "L":
            if str(num[-1]) == '1':
                continue
            num[now] = 0
            now += 1
            num[now] = 1
        else:
            if str(num[-1]) == '1':
                continue
            now += 1
            num[now] = 1
    for i in range(par):
        num[i] = str(num[i])
    print(int("".join(num),2))


def maxx(n):
	return n&-n
n,q=map(int,input().split())
root=n//2+1
while q>0:
	x=int(input())
	s=input()

	for i in s:
		if i=='U' and x!=root:
			p=x+maxx(x)
			if x==p-maxx(p)//2:
				x=p
			else:
				x=x-maxx(x)
		elif i=='L':
			x=x-maxx(x)//2
		elif i=='R':
			x=x+maxx(x)//2
	q=q-1
	print(x)

#Bhargey Mehta (Sophomore)
#DA-IICT, Gandhinagar
import sys, math, queue
#sys.stdin = open("input.txt", "r")
MOD = 10**9+7
sys.setrecursionlimit(1000000)

def hgt(x):
    if x == 0: return -1
    h = 0
    while x&1 != 1:
        h += 1
        x = x>>1
    return h

def up(x):
    h = hgt(x)
    g = x + (1<<h)
    if g > 0 and g < N and hgt(g) == h+1:
        return g
    g = x - (1<<h)
    if g > 0 and g < N and hgt(g) == h+1:
        return g
    return x

def left(x):
    h = hgt(x)
    if h == 0:
        return x
    g = x - (1<<(h-1))
    if g > 0:
        return g
    return x

def right(x):
    h = hgt(x)
    if h == 0:
        return x
    g = x + (1<<(h-1))
    if g < N:
        return g
    return x

N, q = map(int, input().split())
N += 1
for _ in range(q):
    p = int(input())
    for c in input():
        if c == 'U':
            p = up(p)
        elif c == 'R':
            p = right(p)
        else:
            p = left(p)
    print(p)