The Tree

You are given an infinite binary tree. The tree has a root, and infinitely many vertices. Each vertex has a left son and a right son, and each vertex except the root has a parent.

Every vertex can be painted in one of $c$ colors or be colorless. Initially, all vertices are colorless.

You need to process two types of queries.

1. color($u$, $x$): paint vertex $u$ with color $x$, then call color($L$, $(x + 1) \bmod c$) for its left son $L$ and color($R$, $(x - 1 + c) \bmod c$) for its right son $R$. This operation repaints the entire (infinite) subtree of vertex $u$. Here $\bmod$ is the remainder operation. If a vertex has already been painted, its color changes to the new one.
2. Given a vertex, output its current color.

The first line contains two integers $q$ and $c$, the number of queries and colors ($1 \leq q \leq 5 \cdot 10^5$, $1 \leq c \leq 10^9$). Each of the next $q$ queries starts with an integer $t_i$, the type of the $i$-th query.

If $t_i = 1$, the next line contains an integer $x$ ($0 \leq x \leq c - 1$), the color to paint the vertex. The line after that contains a non-empty string $s_i$ of the characters 'L' and 'R', the path from the root to vertex $u$. 'L' means going to the left son, and 'R' means going to the right son.

If $t_i = 2$, the next line contains a path string $s_i$ in the same format, describing the vertex whose color should be output.

The sum of the lengths of the paths of all queries does not exceed $5 \cdot 10^5$.

For each query of the second type, print the color of the corresponding vertex on a separate line. If the vertex is colorless, print $-1$.