AT_tkppc2015_i.重要証拠 (Important evidence)

joisino 姐姐听说学校里有一位高中生侦探，于是去找他。
见面后发现，这位侦探似乎陷入了困境。
因为他发现了一台可能作为案件关键证据的电脑，但数据已经被移除。
幸运的是，电脑上的操作日志还保存着，若能运用这些日志恢复数据，就能快速解决案件。
joisino 姐姐因为编程能力出众，被委托来恢复这些数据。

操作过程如下：

1. 一开始，有 $T$ 种不同的数据，编号从 $1$ 到 $T$。每种数据由一个位串 $S_i$ 表示。
2. 之后重复执行以下三种操作中的某一些：
   1. 合并两个数据。合并后的数据是其位串的拼接，即 $S_a+S_b$。合并后，所有引用到 $a$ 和 $b$ 的变量都将指向这个新数据。如果 $e$ 和 $f$ 都指向同一数据，而后再将 $e$ 和 $g$ 合并，那么 $e$、$f$、$g$ 都将指向新数据。如果 $a$ 和 $b$ 已经合并，则跳过此操作。
   2. 撤销操作，所有数据回到第 $k$ 次操作后的状态。这里的操作包括合并、撤销及输出。
   3. 输出某个数据中的最大连续 $0$ 的数量。这部分信息是案件中被删除的数据，也是解开谜团的关键。

joisino 姐姐利用她的编程技巧，根据日志记录编写了一个程序来恢复数据。

输入通过标准输入提供，格式如下：

• 第一行一个整数 $T$（$1 \le T \le 10^5$），表示数据种类的数量。
• 第二行一个位串 $A$（$1 \le \text{length}(A) \le 10^5$），后续将用到。
• 接下来的 $T$ 行中，每行包含两个整数 $L_i$ 和 $R_i$（$1 \le L_i \le R_i \le \text{length}(A)$），代表第 $i$ 种数据的位串 $S_i$ 是 $A$ 从第 $L_i$ 个字符到第 $R_i$ 个字符。
• 下一行一个整数 $Q$（$1 \le Q \le 10^5$），是日志的记录数量。
• 接下来的 $Q$ 行中，每行包含 $2$ 或 $3$ 个整数，它们按时间顺序记录了日志信息。
  • 若有 $2$ 个整数：
    • 若第一个数字是 $0$，那么第二个数字表示 $a_i$（$1 \le a_i \le T$），这是要输出数据 $a_i$ 中最大连续 $0$ 的数量。如果没有 $0$，就输出 $0$。
    • 若第一个数字是 $1$，那么第二个数字表示 $K$（$0 \le K \le $ 当前已处理的查询数），将所有数据回到第 $K$ 次操作后的状态。
  • 若有 $3$ 个整数：
    • 第一个数字是 $2$，接下来的两个数字是 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le T$），表示合并数据 $a_i$ 和 $b_i$。如果这两个数据已经合并，则忽略此操作。

参考输入格式说明，输出时在每个输出结果末尾加一个换行符。

配分

本题包括部分得分机会。

• 数据集 1 满足 $Q \le 50$，$\text{length}(A) \le 50$，$T \le 50$，正确处理可得 10 分。
• 数据集 2 无附加限制，正确解决可得 150 分。

本翻译由 AI 自动生成