在遥远的国度，驴子（Donkey）总是喋喋不休。有时，他觉得应该重复自己之前说过的话。他以一种特定的方式重复他的短语，即每个字母都翻倍（例如，aabcb 变成了 aaaabbccbb）。给定一个长度为 $n$ 的字符串 $s$ 作为驴子最初的短语，有两种类型的事件：

• 驴子改变了他的短语，重复了其中的一部分。具体来说，他选择从位置 $l$ 到 $r$ 的某个子串并将其翻倍。（例如，如果字符串是 aabc，驴子重复从第 2 位到第 3 位的子串，得到的短语变为 aaabbc）。
• 史莱克（Shrek）无法记住驴子说的所有话。他想知道驴子当前短语中第 $i$ 个字母是什么。

注意，第一类事件会改变驴子的短语。史莱克需要帮助来处理驴子无穷无尽的问题，以便他能保持内心的平静！

输入格式

第一行包含两个整数 $n$ 和 $q$ —— 字符串 $s$ 的长度和事件的数量。 第二行包含字符串 $s$，由小写英文字母组成 —— 驴子最初的短语。 接下来的 $q$ 行包含题目描述的事件。

• $1 \ l \ r$ —— 第一类事件。
• $2 \ i$ —— 第二类事件。

数据范围

$1 \le n, q \le 2 \cdot 10^5$ $1 \le l \le r \le 10^{18}$ $1 \le i \le 10^{18}$ 短语的长度不会超过 $10^{18}$ 所有索引在查询时均不超过当前 $|s|$ 的长度。

输出格式

对于每个第二类事件，在单独的一行中打印答案。

样例

样例输入 1

4 7
abac
2 2
2 3
1 2 3
2 3
2 4
2 5
2 6

样例输出 1

b
a
b
a
a
c

样例输入 2

5 4
shrek
1 1 2
2 7
1 1 7
2 7

样例输出 2

k
h

说明

在第一个样例中，驴子的短语从 abac 变为 abbaac。 在第二个样例中，驴子的短语从 shrek 变为 sshhrek，然后变为 sssshhhhrreekk。