Complete Binary Tree에서의 경로

T는 n개의 정점으로 이루어진 완전 이진 트리이다. 이는 정확히 하나의 정점이 루트이고, 각 정점은 리프(자식이 없음)이거나 내부 정점(정확히 두 자식을 가짐)임을 의미한다. 완전 이진 트리의 모든 리프는 깊이(루트로부터의 거리)가 같다. 따라서 n은 n + 1이 2의 거듭제곱이 되도록 하는 수이다.

그림에서 n = 15인 완전 이진 트리를 볼 수 있다.

정점에는 다음과 같은 특별한 재귀적 방식으로 1부터 n까지 번호가 매겨진다. 먼저 왼쪽 서브트리의 모든 정점에 재귀적으로 번호를 부여하고(현재 정점이 리프가 아닌 경우), 그다음 현재 정점에 번호를 부여한 뒤, 오른쪽 서브트리의 모든 정점에 재귀적으로 번호를 부여한다(존재하는 경우). 그림의 정점들은 정확히 이 알고리즘을 사용하여 번호가 매겨져 있다. 완전 이진 트리의 각 크기에 대해 모든 정점에 번호를 부여하는 방법이 정확히 하나 존재함은 분명하다. 이러한 번호 매기기 방식을 대칭적이라고 한다.

주어진 n에 대해 트리에 관한 q개의 쿼리에 답하는 프로그램을 작성해야 한다.

각 쿼리는 정수 ui (1 ≤ ui ≤ n)와 문자열 si로 이루어진다. 여기서 ui은 정점의 번호이고, si은 이 정점에서 시작하는 경로를 나타낸다. 문자열 si에는 각각 왼쪽 자식, 오른쪽 자식, 부모로 이동한다는 뜻의 'L', 'R', 'U' 이외의 문자가 포함되지 않는다. ui이 경로가 시작되는 정점임을 고려하여, si의 문자들을 왼쪽에서 오른쪽 순서로 처리해야 한다. 어떤 문자를 처리하는 것이 불가능하다면(예를 들어 리프의 왼쪽 자식으로 이동하려는 경우), 그 문자를 건너뛰어야 한다. 답은 si이 나타내는 경로가 끝나는 정점의 번호이다.

예를 들어, ui = 4이고 si = «UURL»이면, 답은 10이다.

첫 번째 줄에는 두 정수 n와 q (1 ≤ n ≤ 1018, q ≥ 1)이 주어진다. n은 n + 1이 2의 거듭제곱이 되도록 하는 수이다.

다음 2q개의 줄은 쿼리를 나타내며, 각 쿼리는 연속된 두 줄로 이루어진다. 이 두 줄 중 첫 번째 줄에는 ui (1 ≤ ui ≤ n)이 주어지고, 두 번째 줄에는 비어 있지 않은 문자열 si가 주어진다. si에는 'L', 'R', 'U' 이외의 문자가 포함되지 않는다.

si (for each i such that 1 ≤ i ≤ q)의 길이의 합은 105를 초과하지 않음이 보장된다.

q개의 수를 출력한다. i-th 수는 i-th 쿼리의 답이어야 한다.