트리

무한 이진 트리가 주어진다. 트리에는 루트가 있고, 무한히 많은 정점이 있다. 각 정점에는 왼쪽 자식과 오른쪽 자식이 있으며, 루트를 제외한 모든 정점에는 부모가 하나 있다.

각 정점은 $c$개의 색 중 하나로 칠해지거나, 색이 없는 상태일 수 있다. 처음에는 모든 정점이 색이 없다.

두 종류의 쿼리를 처리해야 한다.

1. color($u$, $x$): 정점 $u$를 색 $x$로 칠한 뒤, 왼쪽 자식 $L$에 대해 color($L$, $(x + 1) \bmod c$)를, 오른쪽 자식 $R$에 대해 color($R$, $(x - 1 + c) \bmod c$)를 호출한다. 이 연산은 정점 $u$의 부분 트리 전체(무한히 많은 정점)를 다시 칠한다. 여기서 $\bmod$는 나머지 연산이다. 이미 칠해진 정점이라도 색은 새 색으로 바뀐다.
2. 정점이 주어지면 그 정점의 현재 색을 출력한다.

첫 줄에 쿼리 개수 $q$와 색의 개수 $c$가 주어진다 ($1 \leq q \leq 5 \cdot 10^5$, $1 \leq c \leq 10^9$). 이어서 $q$개의 쿼리가 주어지며, 각 쿼리는 정수 $t_i$로 시작한다.

$t_i = 1$이면 다음 줄에 칠할 색 $x$ ($0 \leq x \leq c - 1$)가 주어진다. 그 다음 줄에는 루트에서 정점 $u$까지의 경로를 나타내는 빈 문자열이 아닌 문자열 $s_i$가 주어진다. 'L'은 왼쪽 자식으로, 'R'은 오른쪽 자식으로 이동함을 뜻한다.

$t_i = 2$이면 다음 줄에 같은 형식의 경로 문자열 $s_i$가 주어지며, 이 경로가 가리키는 정점의 색을 출력해야 한다.

모든 쿼리의 경로 길이 합은 $5 \cdot 10^5$을 넘지 않는다.

두 번째 종류의 쿼리마다 해당 정점의 색을 한 줄에 하나씩 출력한다. 정점에 색이 없으면 $-1$을 출력한다.