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

Source: codeforces | Difficulty: HARD
Tags: Tree algorithms

Bit manipulation


Solutions:
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)
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)


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)


import math
p2 = [1] * 64
for i in range(1, 64):
	p2[i] = p2[i - 1] * 2

def find_level(x):
	x0 = 1
	for i in range(max_level + 1):
		if (x - x0) % (x0 * 2) == 0:
			return i
		x0 *= 2

def move_U(number):
	cur_lv = find_level(number)
	if cur_lv == max_level:
		return number
	x0 = p2[cur_lv]
	seg = x0 * 2
	index = (number - x0) // seg
	return x0 * 2 + index // 2 * (seg * 2)

def move_L(number):
	cur_lv = find_level(number)
	if cur_lv == 0:
		return number
	x0 = p2[cur_lv]
	seg = x0 * 2
	index = (number - x0) // seg
	return x0 // 2 + index * 2 * (seg // 2)

def move_R(number):
	cur_lv = find_level(number)
	if cur_lv == 0:
		return number
	x0 = p2[cur_lv]
	seg = x0 * 2
	index = (number - x0) // seg
	return x0 // 2 + (index * 2 + 1) * (seg // 2)

def move(s, num):
	if s == 'U':
		return move_U(num)
	if s == 'L':
		return move_L(num)
	return move_R(num)

def process(S, num):
	for s in S:
		num = move(s, num)
	return num
(n, q) = map(int, input().split())
max_level = int(math.log2(n + 1)) - 1
ans = ''
for _ in range(q):
	num = int(input())
	S = input()
	ans += str(process(S, num)) + '\n'
print(ans)


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)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10)]
pp = [0] * 10

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				pp[i] += 1
				prime[i] = False
		p += 1

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = arr[mid]
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			right = mid - 1
		else:
			res = arr[mid]
			left = mid + 1
	return res
(n, k) = map(int, input().split())
prev = defaultdict(int)
for ik in range(k):
	cur = int(input())
	s = list(input())
	t = 2
	while cur % t == 0:
		t *= 2
	t //= 4
	for i in range(len(s)):
		if cur == (n + 1) // 2:
			if s[i] == 'U':
				continue
			else:
				if s[i] == 'L':
					cur -= t
				else:
					cur += t
				t //= 2
		elif cur % 2 == 1:
			if s[i] == 'U':
				if cur & 2 == 0:
					cur += 1
				else:
					cur -= 1
				t = 1
		elif s[i] == 'L':
			cur -= t
			t //= 2
		elif s[i] == 'U':
			if cur & t * 4 == 0:
				cur += t * 2
			else:
				cur -= t * 2
			t *= 2
		else:
			cur += t
			t //= 2
	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)


def mask(n):
	if not n:
		return 0
	m = 1
	while not m & n:
		m *= 2
	return m
(n, T) = map(int, input().split())
for t in range(T):
	cur = int(input())
	for ch in input():
		m = mask(cur)
		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)


import math
temp = list(map(int, input().split()))
(N, q) = (temp[0], temp[1])
for j in range(0, q):
	u = int(input())
	S = input()
	k = (N + 1) // 2
	n = int(math.log(N + 1, 10) / math.log(2, 10)) - 1
	dup_n = n
	store = [k]
	while u != k:
		n -= 1
		if u > k:
			k += 2 ** n
		else:
			k -= 2 ** n
		store.append(k)
	for i in range(0, len(S)):
		if S[i] == 'R':
			n -= 1
			if n == -1:
				n = 0
				continue
			k += 2 ** n
		elif S[i] == 'L':
			n -= 1
			if n == -1:
				n = 0
				continue
			k -= 2 ** n
		else:
			if n == dup_n:
				continue
			store.pop()
			k = store[len(store) - 1]
			n += 1
			continue
		store.append(k)
	print(k)


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 sys import stdin, stdout

def find(number, aim, cnt, up):
	if aim == number:
		if cnt:
			return (number - cnt // 4 - 1, number + cnt // 4 + 1, up)
		else:
			return (number, number, up)
	if aim > number:
		return find(number + cnt // 4 + 1, aim, cnt // 2 - 1, number)
	else:
		return find(number - cnt // 4 - 1, aim, cnt // 2 - 1, number)
(n, q) = map(int, stdin.readline().split())
for i in range(q):
	v = int(stdin.readline())
	s = stdin.readline().strip()
	for f in s:
		(l, r, u) = find(n // 2 + 1, v, n - 1, n // 2 + 1)
		if f == 'L':
			v = l
		elif f == 'R':
			v = r
		else:
			v = u
	stdout.write(str(v) + '\n')


def l(a):
	b = bin(a)[2:]
	b = '0' * (e - len(b)) + b
	d = len(b)
	for i in range(d - 1, -1, -1):
		if b[i] == '1':
			c = d - 1 - i
			break
	if c == 0:
		return -1
	return a - 2 ** (c - 1)

def r(a):
	b = bin(a)[2:]
	b = '0' * (e - len(b)) + b
	d = len(b)
	for i in range(d - 1, -1, -1):
		if b[i] == '1':
			c = d - 1 - i
			break
	if c == 0:
		return -1
	return a + 2 ** (c - 1)

def u(a):
	b = bin(a)[2:]
	b = '0' * (e - len(b)) + b
	d = len(b)
	for i in range(d - 1, -1, -1):
		if b[i] == '1':
			c = d - 1 - i
			break
	if c == d - 1:
		return -1
	elif b[d - 1 - c - 1] == '0':
		return a + 2 ** c
	else:
		return a - 2 ** c
(n, q) = list(map(int, input().split()))
e = len(bin(n)[2:])
for i in range(q):
	a = int(input())
	b = input()
	for i in range(len(b)):
		if b[i] == 'U':
			c = u(a)
			if c != -1:
				a = c
		elif b[i] == 'R':
			c = r(a)
			if c != -1:
				a = c
		elif b[i] == 'L':
			c = l(a)
			if c != -1:
				a = c
	print(a)


[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))


(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))


from os import path
import sys
from heapq import heappush, heappop, heapify
from functools import cmp_to_key as ctk
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('a')
file = 1

def solve():
	(n, q) = mi()
	x = int(log(n + 1, 2))
	root = 1 << x - 1
	for i in range(q):
		u = ii()
		s = si()
		pos = 'U'
		if u < root:
			pos = 'L'
		if u > root:
			pos = 'R'
		s1 = bin(u)[2:]
		s1 = '0' * (x - len(s1)) + s1
		s1 = list(s1)
		for j in s:
			for k in range(x - 1, -1, -1):
				if s1[k] == '1':
					f = k
					break
			if j == 'L':
				if f == x - 1:
					continue
				s1[f] = '0'
				s1[f + 1] = '1'
			elif j == 'R':
				if f == x - 1:
					continue
				s1[f + 1] = '1'
			else:
				if f == 0:
					continue
				if s1[f - 1] == '1':
					s1[f] = '0'
				else:
					s1[f - 1] = '1'
					s1[f] = '0'
		s1 = ''.join(s1)
		print(int(s1, 2))
if file:
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


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)
	if not 1 << l & x > 0:
		return x + (1 << l - 1)
	return x - (1 << l - 1)

def left(x):
	l = lev(x)
	if l == 1:
		return 0
	return x - (1 << l - 1) + (1 << l - 2)

def right(x):
	l = lev(x)
	if l == 1:
		return 0
	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)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, q) = map(int, input().split())
x = n + 1
l = 0
while x > 1:
	x //= 2
	l += 1
for i in range(q):
	a = int(input())
	s = input()
	for j in s:
		lv = 1
		a1 = a
		while a1 % 2 == 0:
			a1 = a1 // 2
			lv += 1
		x = 2 ** lv
		q = x // 2
		p = q // 2
		y = (a - q) // x + 1
		if j == 'U':
			if lv == l:
				pass
			elif y % 2:
				a = (2 * a + x) // 2
			else:
				a = (2 * a - x) // 2
		elif j == 'L':
			if lv == 1:
				pass
			else:
				z = 2 * (y - 1)
				a = p + z * q
		elif lv == 1:
			pass
		else:
			z = 2 * (y - 1)
			a = p + (z + 1) * q
	print(a)


def main():
	(n, q) = map(int, input().split())
	for _ in range(q):
		node = int(input())
		s = input()
		for i in s:
			if i == 'L':
				if node % 2:
					continue
				k = node & -node
				node -= k
				k //= 2
				node += k
			if i == 'R':
				if node % 2:
					continue
				k = node & -node
				k //= 2
				node += k
			if i == 'U':
				if node == (n + 1) // 2:
					continue
				k = node & -node
				node -= k
				k *= 2
				node |= k
		print(node)
	return
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]
			elif t & ii[ti]:
				t ^= ii[ti]
			ti -= 1
			t |= ii[ti]
		r.append(t)
	return '\n'.join(map(str, r))
print(main())


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 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) = 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)
solve()


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
for _ in range(q):
	u = int(input())
	s = input()
	for comm in s:
		k = 1
		while True:
			if k & u:
				break
			k <<= 1
		if comm == 'L':
			if k != 1:
				u -= k
				u += k >> 1
		elif comm == 'R':
			if k != 1:
				u += k >> 1
		elif comm == 'U':
			nu = u - k
			nu |= k << 1
			if nu <= n:
				u = nu
	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)


def pow2(n):
	j = 0
	while n % 2 == 0:
		n //= 2
		j += 1
	return j
(n, q) = map(int, input().split())
for j in range(q):
	u = int(input())
	s = input()
	for k in range(len(s)):
		num = pow2(u)
		if s[k] == 'R' and num != 0:
			u = u + 2 ** (num - 1)
		elif s[k] == 'L' and num != 0:
			u = u - 2 ** (num - 1)
		elif s[k] == 'U' and u != (n + 1) // 2:
			m1 = u + 2 ** num
			m2 = u - 2 ** num
			if pow2(m1) == num + 1:
				u = m1
			else:
				u = m2
	print(u)


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
			elif bit_pos > 0:
				new_v = v & ~(1 << bit_pos) | 1 << bit_pos - 1
			else:
				new_v = 0
		elif 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():
	main()
__starting_point()


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)


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)


import sys, math, queue
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)


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
		elif 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 sys
(n, q) = map(int, input().split())
top = len(bin(n >> 1)) - 2
ans = [1] * q
for i in range(q):
	v = int(input())
	s = input()
	if n == 1:
		continue
	for h in range(top + 1):
		if v & 1 << h:
			break
	for c in s:
		if h == top and c == 'U' or (h == 0 and c != 'U'):
			continue
		if c == 'U':
			v -= 1 << h
			h += 1
			v |= 1 << h
		elif c == 'L':
			v -= 1 << h
			h -= 1
			v |= 1 << h
		else:
			h -= 1
			v |= 1 << h
	ans[i] = v
print(*ans, sep='\n')


import sys
import bisect
from bisect import bisect_left as lb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0

def setting(s):
	if s == '0':
		return -1
	i = len(s) - 1
	cc = 0
	while i >= 0 and s[i] == '0':
		cc += 1
		i -= 1
	return cc

def hnbhai(tc):
	(n, q) = sd()
	up = n + 1
	x = len(bin(n)[2:]) - 1
	for i in range(q):
		v = sb()
		s = sa()
		for j in s:
			temp = bin(v)[2:]
			abe = setting(temp)
			if j == 'U':
				if abe >= x:
					continue
				p = v + (1 << abe)
				n = v - (1 << abe)
				x1 = setting(bin(p)[2:])
				x2 = setting(bin(n)[2:])
				if x1 == abe + 1:
					v = p
				else:
					v = n
			elif j == 'L':
				if abe <= 0:
					continue
				v = v - (1 << abe - 1)
			else:
				if abe <= 0:
					continue
				v = v + (1 << abe - 1)
		print(v)
for _ in range(1):
	hnbhai(_ + 1)


import sys
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue
from math import *
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7

def bit(n):
	if n == 0:
		return 0
	val = 1
	while val & n == 0:
		val *= 2
	return val
(n, q) = il()
x = n + 1
for i in range(q):
	t1 = ii()
	for j in ip():
		val = bit(t1)
		if j == 'U':
			tem = t1 - val | val * 2
			if tem < n:
				t1 = tem
		elif j == 'L' and val > 1:
			t1 -= val // 2
		elif j == 'R' and val > 1:
			t1 += val // 2
	print(t1)


def lvl(val):
	tot = 1
	curr = -1
	while val % tot == 0:
		curr += 1
		tot *= 2
	return [curr, val * 2 // tot, tot // 2]
(n, q) = map(int, input().split())
for _ in range(q):
	curr = int(input())
	(l, v, pw) = lvl(curr)
	s = input()
	for j in s:
		if j == 'U':
			if v % 4 == 3:
				curr = curr - pw
			elif curr + pw <= n:
				curr = curr + pw
		elif j == 'R':
			if l > 0:
				curr = curr + pw // 2
		elif j == 'L':
			if l > 0:
				curr = curr - pw // 2
		(l, v, pw) = lvl(curr)
	print(curr)