动态二叉树
题号：NC264034
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

纸质题面中的样例有误，请以网页显示为准。

最初，有一棵只有一个节点的二叉树，编号为 1。

你需要处理 n 次操作：

第一类操作会给出一个编号 p 及一个字符 c，表示新加入一个节点，成为编号为 p 的节点的子节点。若 c = \texttt{L} ，则表示新节点为左子节点；若 c = \texttt{R}，则表示新节点为右子节点。新加入节点的编号为加入它之前的节点总数加 1。

第二类操作会给出一个编号 x，表示询问编号为 x 的节点的右侧第一个节点的编号。

请依次处理全部操作，并回答所有询问。

输入描述:

第一行一个正整数 n (1 \leq n \leq 5 \cdot 10^5)，表示操作次数。

随后 n 行，每行给出一次操作：

若为第一类操作，则输入格式形如 \texttt{1 p c}，保证编号为 p 的节点存在，且不存在两次操作一的参数完全相同。保证 c 为 \texttt{L} 或者 \texttt{R}。

若为第二类操作，则输入格式形如 \texttt{2 x}，保证编号为 x 的节点存在。

输出描述:

对于每次第二类操作，按输入顺序依次输出一行一个整数表示答案。

若询问的节点右侧没有任何节点，则输出一行一个整数 -1。
示例1

输入

复制 
9
1 1 R
1 1 L
2 3
1 2 R
2 4
1 3 L
2 5
1 3 R
2 5

输出

复制 
2
-1
4
6

说明

树的最终形态如图所示：