U296411 [NEERC 2022 D] The Tree

[原题面](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-team-spb-2022-statements-english.pdf)

你有一棵无限满二叉树，每个节点初始无颜色，总共有 $c$ 种颜色。 你需要实现两种操作共 $q$ 次： 1. `color(int x，string u)` 1. `ask(string s)` 我们建立一个由 `L` 和 `R` 组成的字符串 $s$ 与树上一个节点的对应关系如下： > 参数 $s$ 为一个由 `L` 和 `R` 构成的字符串，表示从根节点开始，按 `L/R` 顺序进入左/右子所到达的节点。（`L` 表示进入左子，`R` 表示右子） 第一种操作为把 $u$ 对应的节点染成 $x$ 颜色，并依次调用 `color(lson(u),(x+1)%c)`，`color(rson(u),(x-1+c)%c)`。（`lson(u)` 表示 $u$ 的左子，`rson(u)` 表示 $u$ 的右子）这一操作会将整个 $u$ 的子树染色。 第二种操作为输出 $s$ 对应节点的颜色，如果无颜色，输出 `-1`。

第一行两个整数 $q,c$，表示询问数和颜色数。 接下来 $2\times q$ 行，每两行表示一个操作。 每组操作的第一行首先有一个数 $op$，表示操作种类。 1. 如果 $op=1$，该行还会输入一个整数 $x$ 表示将要染的颜色，第二行输入一个字符串，表示染的节点。 1. 如果 $op=1$，直接在第二行输入一个字符串，表示查询的节点。

对于每个操作二，输出一个整数作为答案，答案之间用换行隔开。

对于 $100\%$ 的数据，$1\le q \le 5\times 10^5$，$1\le c \le 10^9$，$0\le x\le c-1$，$op\in \{1,2\}$。