题目描述

潮汐站使用 0 和 1 记录信号。定义两类记录串 $U_i,D_i$：

对于 $i\ge 1$，有

其中 $+$ 表示字符串拼接。例如，$U_1=0111000$，$D_1=11001111$。

给定层数 $n$ 和模式 $c$。当 $c=\mathrm{U}$ 时，目标记录串 $W=U_n$；当 $c=\mathrm{D}$ 时，$W=D_n$。字符串下标从 $1$ 开始。

你需要回答 $q$ 个互相独立的询问：

• 1 k：求 $W$ 的第 $k$ 个字符；
• 2 x：考虑 $W$ 的前 $x$ 个字符，求其中最长的、所有字符都相同的连续子串长度。

记录串可能极长，不能直接完整写出。

输入格式

从文件 tide.in 中读取数据。

第一行输入三个量 $n,c,q$，分别表示层数、模式和询问数。

接下来 $q$ 行，每行输入一个询问，格式为 1 k 或 2 x。

输出格式

输出到文件 tide.out 中。

对于每个询问输出一行：

• 对于 1 k，输出第 $k$ 个字符；
• 对于 2 x，输出所求最长连续子串的长度。

每个询问的答案由上述定义唯一确定。

2 U 5
1 1
1 8
2 7
2 16
2 25

0
1
3
4
4

0 D 3
1 2
2 1
2 2

1
1
2

样例解释

样例 #1 中，

U_2 = 0111000111001111000111000

它的前 $7$ 个字符为 0111000，最长相同字符连续段是 111；前 $16$ 个字符以 1111 结尾，因此对应答案为 $4$。

样例 #2 中，$D_0=11$。

数据规模与约定

对于所有数据，保证：

• $0\le n\le 10^9$；
• $c$ 为 U 或 D；
• $1\le q\le 2\times 10^5$；
• 每个询问的类型为 $1$ 或 $2$；
• 对于 1 k，$1\le k\le\min(10^{18},|W|)$；
• 对于 2 x，$1\le x\le\min(10^{18},|W|)$。

其中，$|W|$ 表示字符串 $W$ 的长度。

本题采用子任务捆绑计分。只有通过某个子任务内的所有测试点，才能获得该子任务的分数。各子任务独立计分。

下发文件

下载三组测试数据，非真实测试数据