AT_tkppc2015_i 重要証拠 (Important evidence)

[problemUrl]: https://atcoder.jp/contests/tkppc/tasks/tkppc2015_i joisinoお姉ちゃんは、この学校に高校生探偵がいることを知り、彼のもとを訪ねることにした。 訪ねると彼は、珍しくとても困っているようだった。 というもの、事件の重要な証拠となりうるパソコンを発見したのだが、肝心のデータが抜き取られていたらしい。 しかし、行われた操作のログは残っているので、それをもとにデータの復元ができれば事件はすぐに解決するという。 joisinoお姉ちゃんは優秀なプログラマーであることを見込まれ、データの復元に取り掛かることにした。 パソコンで行われていた操作は以下のようなものである。 3. まず、データ$ 1 $からデータ$ T $までの$ T $種類のデータがある。 $ i $種類目のデータは、それぞれあるビット列$ S_i $で構成されている。 4. 続いて、以下の3種類の行動を何回か行う。 > 1. あるデータを以下の方法で別のデータと結合する。 > （結合後のデータのビット列は$ S_a+S_b $となり、$ a $番目と$ b $番目のデータはこれをさすようになる。ただし、この足し算はビット列を文字列とみなして行うものとする。たとえば、$ e $と$ f $が同じデータをさしている場合に、$ e $と$ g $を結合すると、$ e $と$ f $と$ g $はすべてこの結合後のデータをさすようになる。また、データ$ a $とデータ$ b $がすでに結合されている場合はこの操作を無視するものとする。） 3. 今までの処理をundoし、全てのデータの状態を$ k $回操作を行った直後の状態に戻す。（ここでいう操作とは、結合、undo、出力のすべてである） > 4. あるデータにおいて、そのビット列の、「連続する$ 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 $つの整数が含まれる。 > 1. 含まれる整数の数が$ 2 $個のとき、最初の数字は$ 0 $か$ 1 $である。 > > 1. 最初の数字が$ 0 $のとき、この次の数字を$ a_i(1≦a_i≦T) $とする。 > > このとき、データ$ a_i $の、「連続する$ 0 $の個数」の最大値を出力せよ。ただし、0がビット列に含まれない場合は0を返すものとする > > 2. 最初の数字が$ 1 $のとき、この次の数字を$ K $とする。 > > このとき、全てのデータは$ K(0≦K≦処理が完了したクエリの個数) $回の操作を行った直後の状況に戻る。 > > 3. 含まれる整数の数が$ 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点が得られる。