問題文
joisino姐姐得知这所学校里有高中生侦探,决定去找他。
拜访时,他看起来很麻烦,显得非常困惑。
原来,他发现了一台可能成为案件重要证据的电脑,但关键数据似乎被抽走了。
然而,由于操作记录被保存,如果能基于这些记录恢复数据,事件将立即解决。
乔伊西诺的姐姐被认可为出色的程序员,决定开始恢复数据。
计算机操作如下。
i每种类型的数据都是位序列S_i。
将一个数据与另一个数据以以下方式合并。 (合并数据的比特为S_a+S_b变为 通过ath 和 由于您拿了第b的数据也指向这一点。 然而,这种加法是将位串视为字符串来实现的。 例如,e和 按字典顺序比较f指向相同数据的情况下,e和 按字典顺序比较g合并后,e和 按字典顺序比较f和 按字典顺序比较g都会指向这个合并后的数据。另外,如果数据a和数据b已经合并,则忽略此操作。)撤销到目前为止的所有处理,将所有数据的状态k恢复到操作刚完成时的状态。(这里所说的操作包括合并、撤销、输出全部) 对某个数据,输出其比特列中“连续的0个数”的最大值。
这个输出正是事件的关键,也是被截取的数据。
优秀的程序员joisino姐姐基于电脑日志,编写了恢复被截取数据的程序。
入力
输入是按以下格式从标准输入给出的。
T A L_1 R_1 L_2 R_2 : L_T R_T Q :
- 第一行是数据的种类T(1≦T≦10^5)。 表示
- 下一步1行,有一个比特列A(1≦length(A)≦10^5)的给出。关于这个用法,将在之后说明。
- 下一步T行,表示分配给各数据的比特列。
其中 在行i行是一个整数L_i(1≦L_i≦length(A)),R_i(L_i≦R_i≦length(A))包含。这意味着S_i是 在A可以得到第L_i从第一个字符开始R_i个字符之前是相等的。 - 下一步1行,日志的数量Q(1≦Q≦10^5)。 表示
- 下一步Q行,日志信息按时间顺序书写。
每行有2个或者3个整数。 - 所含整数的数量为2个时,第一个数字是0或1。
- 第一个数字是0时,下一个数字为a_i(1≦a_i≦T)。
这个时候,数据a_i中,“连续的0的数量”的最大值。注意,如果比特列中不包含0,则返回0。 - 第一个数字是1时,下一个数字为K。
这个时候,所有数据都会恢复到进行K(0≦K≦処理が完了したクエリの個数)次操作后的位置。 - 所含整数的数量为3为2时,第一个数字是a_i,b_i。
这个时候,数据a_i(1≦a_i≦T)这表示将其合并到数据b_i(1≦b_i≦T)中。不过,需要注意,如果a_i和 按字典顺序比较b_i已经被合并,则必须忽略。
配点
该题有部分得分。
- 数据集 1 是 如果您遇到Q ≦50,length(A)≦50,T≦50并正确回答,您将获得10分。
- 在数据集2中没有额外约束,如果正确完成,可以得150分。
出力
请参阅“输入”部分。
另外,在输出末尾放置一个换行符。
入力例1
5 11111 2 3 2 3 2 4 4 4 4 5 5 2 5 2 0 4 0 1 2 5 5 1 2
出力例1
0 0