A - 足し算の宿題 (A + B Home work)

Time Limit: 1 sec / Memory Limit: 64 MB

問題文

joisinoお姉ちゃんにはかわいい妹がいる。
今は夏休みなので、妹は宿題をやっているのだが、あまりにも同じ種類の問題が続くので飽きてしまったようだ。
仕方がないのでjoisinoお姉ちゃんは妹の宿題を手伝うことにした。

この宿題はN問の足し算の問題で、i(1 ≦ i ≦ N)番目の問題はA_iとB_iを足した数を答えよというものである。
こんなめんどくさい問題はjoisinoお姉ちゃんも手計算ではやりたくなかったので、プログラムでこの問題を解くことにした。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1
A_2 B_2
：
A_N B_N
  • 1行目には、問題の数N(1 ≦ N ≦ 10^5)が与えられる。
  • 2行目からのN行のうちi行目にはA_i,B_i(0 ≦ A_i,B_i ≦ 10^8)が与えられる。

配点

この問題に部分点はない。 正解すると40点を得られる。

出力

出力はN行からなる。
i行目にはi番目の問題の答えを出力せよ。
出力の末尾にも改行を入れること。

入力例1

2
10 3
5 11

出力例1

13
16

この場合、問題は2問あり、1問目の正解は10+3で13、2問目の正解は5+11で16となる。

入力例2

3
5 16
59 14
3 17

出力例2

21
73
20

この場合、問題は3問あり、1問目の正解は21、2問目の正解は73、3問目の正解は20となる。

入力例3

10
67 41
0 34
24 69
58 78
64 62
45 5
27 81
91 61
42 95
36 27

出力例3

108
34
93
136
126
50
108
152
137
63
B - 金髪の少女 (Blonde girls)

Time Limit: 1 sec / Memory Limit: 64 MB

問題文

妹の宿題を手伝って疲れたので、joisinoお姉ちゃんは少しテレビを見ることにした。

しかし、ふと気がつくとjoisinoお姉ちゃんはイギリスのような町にいた。
どうやら知らない間に違う世界にやってきてしまったようだ。

そこにはN人の金髪の少女がいたが、joisinoお姉ちゃんは金髪の少女が大好きなので、彼女たちを抱きしめたいと思った。
しかし、人数が多いので、すべての少女を抱きしめることはできない。
そこで、joisinoお姉ちゃんは彼女たちの中でもっとも金髪の美しさが大きい少女を抱きしめることにした。
このとき、少女i(1 ≦ i ≦ N)の金髪の美しさはA_iである。

しかし、少女の数があまりにも多いので、joisinoお姉ちゃんは最も美しい金髪を持つ少女を探すプログラムを書こうと思った。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1
A_2
：
A_N
  • 1行目には、少女の人数N(1 ≦ N ≦ 10^5)が与えられる。
  • 2行目からのN行のうちi行目にはi番目の少女の金髪の美しさA_i(0 ≦ A_i ≦ 10^9)が与えられる。

配点

この問題に部分点はない。 正解すると40点を得られる。

出力

最も金髪の美しさが大きい少女の番号を出力せよ。
また、そのような少女が複数いるときはその少女たちの番号の中で最も小さいものを出力すること。
出力の末尾にも改行を入れること。

入力例1

2
123
146

出力例1

2

この場合、少女は2人いて、1番目の少女の金髪の美しさは123、2番目の少女の金髪の美しさは146なので、2番目の少女がもっとも美しい金髪を持つ。

入力例2

4
124
23
145
145

出力例2

3

この場合、少女は4人いて、3番目と4番目の少女がもっとも美しい金髪を持っているので、より番号が小さい3を出力する。

入力例3

10
41
467
334
0
169
224
478
358
462
464

出力例3

7
C - お姉ちゃんって呼んで (Call me sister)

Time Limit: 1 sec / Memory Limit: 64 MB

問題文

joisinoお姉ちゃんは少し疲れたので、近くにあった喫茶店で休むことにした。
ここで、joisinoお姉ちゃんは、あるウェイトレスがとても気に入ったので、彼女に「お姉ちゃん」と呼んでもらいたいと思った。
しかし、彼女に「お姉ちゃん」と呼んでもらえるかどうかは、彼女の機嫌にかかわっている。

これからこの喫茶店では、N個の出来事が起こる。
それぞれの出来事には1～Nまでの番号が割り振られていて、出来事i(1≦i≦N)は、時刻T_iに起こり、ウェイトレスの機嫌にK_iが足される。
なお、同じ時刻に二つ以上の出来事が起こることはない
そして、ウェイトレスの機嫌がM以上の時だけ、お姉ちゃんと呼んでもらうことができる。
現在の時刻は0であり、現在のウェイトレスの機嫌は0である。

joisinoお姉ちゃんは、時刻Sにこの喫茶店を出る。
joisinoお姉ちゃんは、店を出るまでの間に「お姉ちゃん」と呼んでもらえる時間がどれだけあるのか知りたいと思い、それを求めるプログラムを作成することにした。
なお、joisinoお姉ちゃんがどのようにして、これから起こる出来事の情報を手に入れたのかは謎である。

入力

入力は以下の形式で標準入力から与えられる。

N M
S
T_1 K_1
T_2 K_2
:
T_N K_N
  • 1行目には、これから起こる出来事の数N(1≦N≦1000)と、お姉ちゃんと呼んでもらえる機嫌の最低値M(0≦M≦10000)が空白区切り書かれている。
  • 2行目には、joisinoお姉ちゃんが喫茶店を出る時刻S(2≦S≦10000)が書かれている。
  • 3行目から続くN行のうちi行目では、これから起こる出来事の情報として、整数T_i(0＜T_i＜S)と、整数K_i(-10000≦K_i＜0,0＜K_i≦10000)が空白区切りで書かれている。
  • i≠jにおいて、T_i≠T_jが保障されている。

配点

この問題に部分点はない。正解すると60点が得られる。

出力

お姉ちゃんと呼んでもらえる時間の合計を1行で出力せよ。
また、出力の末尾には改行を入れること。

入力例1

5 20
20
5 16
8 -4
3 9
18 2
12 -3

出力例1

9
  • 時刻5から時刻12までの7と、時刻18から、喫茶店を出る時刻20までの2の間で、機嫌が20以上となっているため、その合計である9を出力する。
D - サポーター (Supporter)

Time Limit: 1 sec / Memory Limit: 64 MB

リジャッジをしました。

問題文

休憩を終えたjoisinoお姉ちゃんは、偶然知り合った冒険者の人とともに、ダンジョンに潜ることにした。
順調な道のりだったが、途中で事故が起き、急いで安全地帯まで向かう必要に迫られた。

このダンジョンは、全ての階層で、南北にR個、東西にC個、全部でR*C個の部屋が格子状に並んでいる。
joisinoお姉ちゃんたちは現在いる階層の、最も北西の部屋にいる。
安全地帯は、現在の階層からN-1回降りた階層の、最も南東の部屋である。

安全地帯の存在する階層以外の各階層にはいくつか穴が存在する。
穴は部屋の中にあり、穴に落ちることで、一つ下の階層に降りることができる。
この時、穴のあった場所が、北西の部屋から、東にx 南にy 進んだ部屋だった場合、落ちた先の部屋も、北西の部屋から東にx 南にy　進んだ部屋である。
なお、落ちた先の部屋にも穴があるということはない。
また、穴のある部屋に入ったときは、必ず落ちなくてはならない。

それぞれの部屋には、危険度というものがある。
この危険度が高ければ高いほど、その部屋を通る危険が大きいことを表す。
穴のある部屋の危険度は0であるが、落ちたあとの部屋の危険度は考慮するものとする。
なお、現在joisinoお姉ちゃんがいる部屋、安全地帯の部屋の危険度は0である。

joisinoお姉ちゃんたちは、できるだけ危険を避けつつ、安全地帯まで移動したい。
そのために、最短経路(西や北に移動しないようにした道順)の中で、通る部屋の危険度の合計が最小となるルートで進むことにした。
優秀なプログラマーであるjoisinoお姉ちゃんは、そのようなルートで進んだ時の、危険度の合計を求めるプログラムを作成することにした。

入力

入力は以下の形式で標準入力から与えられる。

N R C
S_1
S_2
:
S_{N*R}
  • 1行目には、通る階層の数N(2≦N≦100)と、階層の大きさを示す整数R(2≦R≦100)とC(2≦C≦100)が、空白区切りで書かれている。
  • 2行目からのN*R行のうち、K*R+1行目からのR行には、現在の階層からK(0≦K≦N-1)回降りた階層の情報が書かれている。 このR行のうちi行目には、長さCの文字列が書かれている。 この文字列は、Hと、0から9までの文字で構成されている。 j番目の文字がHである場合、それは、北西の部屋から東にj-1 南にi-1進んだ部屋に穴があることを示す。 j番目の文字が0である場合、それは、北西の部屋から東にj-1 南にi-1進んだ部屋がスタート地点もしくはゴール地点であることを示す。 j番目の文字が1から9の間の数字であった場合、それは、北西の部屋から東にj-1 南にi-1進んだ部屋の危険度がその数字であることを示す。
  • 全ての入力において、安全地帯へ到達するルートが一つ以上あることが保障されている。

配点

この問題に部分点はない。正解すると60点が得られる。

出力

危険度の合計の最小値を一行で出力せよ。
また、出力の末尾には改行を入れること。

入力例1

3 3 3
06H
H14
257
337
15H
2H8
829
653
470

出力例1

9
  • 南→穴に落ちる→東→東→穴に落ちる→南 と移動することで、危険度の合計を最小化できる。

入力例2

2 5 3
013
871
7HH
163
92H
959
248
792
447
550

出力例2

14
E - 不可視境界線 (The Invisible Borderline)

Time Limit: 2 sec / Memory Limit: 128 MB

この問題の入力例1の図が間違っていましたが、修正しました。
また、入力例2のほうはジャッジシステムで使っているものと異なっていたので、変更しました。ただ、今までのテストケースも問題の条件は満たしていました。
リジャッジも終わりました。

問題文

ダンジョンを抜けるとそこは学校だった。
その学校は部活動が盛んなようだったので、joisinoお姉ちゃんは部活見学をしてみることにした。

はじめに入った部活では床に魔方陣が描かれていた。
何をしているのかたずねてみると、異世界についての研究をしているという。
彼女たちの話によると、この世界を含めたN個の世界が存在していて、それらはN-1個の不可視境界線と呼ばれるゲートのようなものでつながっているということである。
また、世界同士はいくつかの不可視境界線を通ることによって互いに行き来できるようになっているらしい。
そして、不可視境界線i(1 ≦ i ≦ N-1)は世界A_i(1 ≦ A_i ≦ N)とB_i(1 ≦ B_i ≦ N)を結んでいるが、通るときにC_i(1 ≦ C_i ≦ 10^9)のダメージを受けるという。

そこで彼女たちはそれぞれの世界について、合計で最も多くのダメージを受けないとたどり着くことのできない世界を探しているらしい。

しかし、世界はたくさんあるので、彼女たちは調べるのがとても大変そうである。
そこでjoisinoお姉ちゃんはこの問題を解くプログラムを書いてあげることにした。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1 C_1
A_2 B_2 C_2
：
A_{N-1} B_{N-1} C_{N-1}
  • 1行目には、世界の数N(1 ≦ N ≦ 10^5)が与えられる。
  • 2行目からのN-1行のうちi行目にはi番目の道の情報が書かれており、A_iとB_iとC_iが空白区切りで与えられる。

配点

この問題に部分点はない。 正解すると80点を得られる。

出力

出力はN行からなる。
i行目にはi番目の世界から最も多くのダメージを受けないとたどり着くことのできない世界の番号を出力せよ。
また、そのような世界が複数あるときはそれらの番号の中で最も小さいものを出力せよ。
出力の末尾にも改行を入れること。

入力例1

3
1 2 10
2 3 15

出力例1

3
3
1

この場合、下の図のように世界はつながっていて、世界1からは世界3へ行く時が25とダメージの合計が最も多く、世界2からは世界3へ行くとき15とダメージの合計が最も多く、世界3からは世界1に行くときが25とダメージの合計が最も多い。

入力例2

5
1 2 15
1 3 15
1 4 5
4 5 10

出力例2

2
3
2
2
2

この場合、下の図のように世界はつながっていて、世界1からは世界2へ、世界2からは世界3へ、世界3からは世界2へ、世界4からは世界2へ、世界5からは世界2へ行くのがもっとも多くダメージを受ける。

入力例3

10
8 3 55
9 1 160
1 4 265
9 5 571
2 9 771
4 7 818
9 10 11
2 8 569
4 6 340

出力例3

3
7
7
3
3
3
3
7
3
3
F - 吹奏楽部 (Brass Band)

Time Limit: 1 sec / Memory Limit: 256 MB

問題文

joisinoお姉ちゃんは次は吹奏楽部に行ってみようと思った。
joisinoお姉ちゃんが興味をもって音楽室に行くと、そこで顧問の先生が困っていた。
joisinoお姉ちゃんは優秀なプログラマーであることを見込まれて、先生から相談を受けた。

相談の内容は以下のとおりである。

  • この吹奏楽部ではN個の楽器が使用されており、それぞれに1～Nまでの番号が割り振られている。楽器i(1≦i≦N)の奏者はi人いる。
  • 楽器iを美しく響かせるため、それを使うi人は、舞台を横にi+1等分した位置に均等に並ぶ必要がある。このようにして、N個の楽器を使う全員が舞台上に横一列に並ぶ。
  • 人の幅は考えないものとするが、二人以上の人が全く同じ位置に立った場合、そのうち最も番号の小さい楽器を使う人だけがその位置に立ち、他の楽器を使う人は舞台に立つことはできない。
  • この吹奏楽コンテストにはM人の審査員がおり、それぞれに1～Mまでの番号が割り振られている。彼らは舞台と平行に並んでいる。
  • 審査員j(1≦j≦M)は、舞台の横の長さを1とした時、舞台の左端から、P_j/Q_j の位置にいる。
  • 審査員にはそれぞれ決まった距離がある。審査員jは自分との距離が決まった距離以内にいる奏者を見ることになっており、その人数はK_jだとわかっている。
  • 練習の参考とするために、それぞれの審査員が見ている人の中で、最もその審査員から遠いところにいる人が演奏している楽器の番号が知りたい。

    • 優秀なプログラマーであるjoisinoお姉ちゃんは、現在分かっている情報(楽器の個数N、審査員の人数M、審査員jの位置P_j/Q_j、見ている奏者の人数K_j)をもとに、審査員jが見る奏者の中で最も遠い人が演奏する楽器の番号を求めるプログラムを作成することにした。

    なお、最も遠い距離にいる奏者が二人の場合、そのうち片方だけが見られるということはあり得ない。また、その二人のうち演奏する楽器の番号が小さいほうを出力せよ。（同じ場合はそのまま出力せよ）

    入力

    入力は以下の形式で標準入力から与えられる。

    . 
    N M
P_1 Q_1 K_1
P_2 Q_2 K_2
:
P_M Q_M K_M
    • 1行目には、楽器の個数N(1≦N≦3*10^4)、審査員の数M(1≦M≦30)が空白区切りで書かれている。
    • 2行目からのM行のうちj行目には、審査員jの位置を表す整数P_j(1≦P_j＜Q_j)　Q_j(2≦Q_j≦N+1)　見る奏者の人数K_jが空白区切りで書かれている。
    • すべての入力において、審査員の見る人数が、奏者全員の人数を超えることはない。

    配点

    この問題には部分点が設定されている。

  • データセット1では、N≦5000を満たし、正解すると15点が得られる
  • データセット2には追加の制約はなく、正解すると105点が得られる

    • 出力

    出力はM行からなる。j行目には、審査員jが見る中で最も遠い奏者が演奏している楽器の番号を出力せよ。
    また、出力の末尾には改行を入れること。

    入力例1

    5 2
3 5 3
1 4 4

    出力例1

    1
2
    • この場合、舞台上には下図のように奏者が並んでいる。（青い線が舞台の端を表し、数字はその番号の楽器を持った奏者がそこにいることを表す）
      審査員1は緑の矢印の位置から、緑の括弧の範囲にいる3人を見ている。括弧内の中で最も遠い奏者は1の奏者なので、1を出力する。
      審査員2は赤の矢印の位置から、赤の括弧の範囲にいる4人を見ている。括弧内の中で最も遠い奏者は2の奏者と5の奏者なので、番号の小さい2を出力する。

    入力例2

    7 5
3 8 7
2 5 12
4 8 7
1 5 13
3 5 6

    出力例2

    1
5
7
4
6
    • この場合、審査員4の見る範囲が舞台の端を超えている。
    G - おおきなかずを作った (I made a huge number)

    Time Limit: 1 sec / Memory Limit: 256 MB

    問題文

    joishinoお姉ちゃんは、のどかな田舎にある小さな分校にやってきた。
    どうやら、この学校では特殊な遊びが流行っているようである。

    遊びのルールは以下の通りである。

  • この遊びは、二人で行われる。
  • まず一人が、いくつかの互いに異なる自然数を選び、それらを小さい順に右から左へと並べていき、連結して新たな数を作る。
  • ここでいう自然数とは、1以上の整数で、先頭に来る数字が0でないものとする。つまり、01や0099などは認められない。
    • （例えば、選んだ自然数が、5 18 48 52 ならば、5248185 という数ができる。）
  • そして作った数を、相手に見せる。
  • 見せられた人は、その数を作ることのできる、もともとの数の組をひとつ予想する。
  • 予想した数の組の中で最大の数が、作られる時に使われた数の組の中で最大の数以下ならば、予想した側の勝ち、そうでなければ、数を作った側の勝ちとなる。

    • joisinoお姉ちゃんは、ある小学生とこの遊びをすることになった。
    この小学生は、連休中にやる気を出して、大きな数を作ってきたようである。
    予想する側になったjoisinoお姉ちゃんは、自身のプライドにかけてこの遊びに勝利したいと思った。
    そしてjoisinoお姉ちゃんは、予想する側が最善を尽くすことで必ず勝利できると気づいた。
    そこで優秀なプログラマーであるjoisinoお姉ちゃんは、与えられた数を元に、その数を作ることのできる数字の組のうち、最大の数がとりうる最小の桁数を計算するプログラムを作成することにした。

    入力

    入力は以下の形式で標準入力から与えられる。

    . 
    N
S
    • 1行目には、与えられる数の桁数N(1≦N≦10^6)が書かれている
    • 2行目には、N桁の数が書かれている。（この数の先頭の数字が0でないことが保障されている）

    配点

    この問題には部分点が設定されている。

  • データセット1は、N(1≦N≦10^4)を満たし、正解すると15点が得られる。
  • データセット2では追加の制約はなく、正解すると125点が得られる。

    • 出力

    与えられた数を作ることのできる数の組の中で、最大の数の桁数が最も小さくなる場合の、その桁数を1行で出力せよ。
    また、出力の末尾には改行を入れること。

    入力例1

    7
5248185

    出力例1

    2
    • 52 48 18 5 という数の組にしたとき、最大の数(52)の桁数が最小(2桁)になる

    入力例2

    9
123456789

    出力例2

    4
    • 1234 567 89 という数の組にしたとき、最大の数(1234)の桁数が最小(4桁)になる。

    入力例3

    20
49260520598009034978

    出力例3

    8
    H - 私、木になります (I become a tree)

    Time Limit: 3 sec / Memory Limit: 256 MB

    問題文

    本校に戻って次の部活を覗いてみると、そこにでは少女がウィスキーボンボンを食べていた。
    そしてjoisinoお姉ちゃんを見つけると、一緒にゲームをしませんかと言った。
    joisinoお姉ちゃんはゲームが大好きなので、もちろん一緒にすることにした。

    そして『私、木になります』というゲームをすることになった。 このゲームではN個の都市とM本の道を使用する。 はじめ、N個の都市はM本の道によって互いに行き来可能なように結ばれている。
    このとき、道i(1 ≦ i ≦ M)は都市A_i(1 ≦ A_i ≦ N)とB_i(1 ≦ B_i ≦ N)を結んでいる。
    そして都市同士が互いに行き来可能なまま道を取り除いていくというゲームである。

    彼女は非常に頭が良いので、ゲームが始まる前からどの道をどのタイミングで取り除くかの計画を立てている。
    この計画はQ個の操作で構成されていて、i(1 ≦ i ≦ Q)番目の操作では道D_i(1 ≦ D_i ≦ M)を取り除こうとする。
    また、取り除く道はゲーム開始時にあるものから選ばれていて、同じ道は複数回取り除かないようになっている。
    しかし今、彼女はウィスキーボンボンを食べて少し酔っているので、この計画通りに道を取り除いていくとゲームのルールに違反してしまうことがある。

    また、彼女はそれぞれの操作iについて重要性G_iというものを持っている。
    そして操作iが失敗した場合、すなわち操作iをすると都市同士が互いに行き来可能でなくなるため、その操作を行わない場合に彼女はG_iだけ落ち込んでしまう。
    よって彼女はゲーム終了時には失敗した操作の重要度の合計だけ落ち込んでいる。

    joisinoお姉ちゃんはあまり彼女に落ち込んでほしくないので、ゲーム中の好きなタイミングでP本以下の道を付け加えることにした。
    ただしゲーム開始時に1本の道で結ばれていた2つの都市の間には道を付け加えることができない。

    このことを行ったとき、joisinoお姉ちゃんはゲーム終了時に彼女がどれだけ落ち込むことになるかの最小値を計算することにした。

    入力

    入力は以下の形式で標準入力から与えられる。

    N M Q P
A_1 B_1
A_2 B_2
：
A_M B_M
D_1 G_1
D_2 G_2
：
D_Q G_Q
    • 1行目には、都市の数N(1 ≦ N ≦ 10^5)とゲーム開始時の道の数M(N-1 ≦ M ≦ 3*10^5)と操作の回数Q(1 ≦ Q ≦ M)と付け加えてよい道の数P(0 ≦ P ≦ 10^9)が空白区切りで与えられる。
    • 2行目からのM行のうちi行目にはi番目の道の情報が書かれており、A_iとB_iが空白区切りで与えられる。
    • M+1行目からのQ行のうちi行目にはi番目の操作の情報が書かれており、D_iとG_i(1 ≦ G_i ≦ 10^9)が空白区切りで与えられる。
    • A_i ≠ B_iが保証されている。
    • i ≠ jにおいてA_i ≠ A_jまたはB_i ≠ B_jが保証されている。
    • i ≠ jにおいてD_i ≠ D_jが保証されている。

    配点

    この問題には部分点がある。

    • データセット1は、N ≦ 10^4、M ≦ 10^4、P = 0を満たし、これに正解すると10点が得られる。
    • データセット2は、P = 0を満たし、これに正解すると10点が得られる。
    • データセット3では追加の制約はなく、これに正解すると120点が得られる。

    出力

    ゲーム終了時の彼女の落ち込みの最小値を答えよ。 出力の末尾にも改行を入れること。

    入力例1

    3 3 2 0
3 1
2 3
2 1
3 15
2 10

    出力例1

    10

    この場合、はじめは上の図のように都市同士はつながっていて、最終的には下の図のような形になる。このとき彼女は道2を取り除くことができず、ゲーム終了時に彼女は10だけ落ち込んでいる。

    入力例2

    4 4 3 1
2 1
2 3
2 4
3 1
4 7
1 17
3 11

    出力例2

    11

    この場合、はじめは上の図のように都市同士はつながっていて、操作2を行う前に都市1と都市4の間に道を作ることで、最終的には下の図のような形になる。このとき彼女は道3を取り除くことができず、ゲーム終了時に彼女は11だけ落ち込んでいる。なお、このケースはデータセット3に含まれている。

    入力例3

    4 6 4 5
3 1
2 1
3 4
4 1
2 3
2 4
5 23
3 18
6 5
4 14

    出力例3

    14

    このテストケースはデータセット3に含まれている。

    I - 重要証拠 (Important evidence)

    Time Limit: 2 sec / Memory Limit: 512 MB

    問題文

    joisinoお姉ちゃんは、この学校に高校生探偵がいることを知り、彼のもとを訪ねることにした。
    訪ねると彼は、珍しくとても困っているようだった。
    というもの、事件の重要な証拠となりうるパソコンを発見したのだが、肝心のデータが抜き取られていたらしい。
    しかし、行われた操作のログは残っているので、それをもとにデータの復元ができれば事件はすぐに解決するという。
    joisinoお姉ちゃんは優秀なプログラマーであることを見込まれ、データの復元に取り掛かることにした。

    パソコンで行われていた操作は以下のようなものである。

  • まず、データ1からデータTまでのT種類のデータがある。
    i種類目のデータは、それぞれあるビット列S_iで構成されている。
  • 続いて、以下の3種類の行動を何回か行う。
  • あるデータを以下の方法で別のデータと結合する。
    • （結合後のデータのビット列はS_a+S_bとなり、a番目とb番目のデータはこれをさすようになる。ただし、この足し算はビット列を文字列とみなして行うものとする。たとえば、eとfが同じデータをさしている場合に、eとgを結合すると、eとfとgはすべてこの結合後のデータをさすようになる。また、データaとデータbがすでに結合されている場合はこの操作を無視するものとする。）
  • 今までの処理をundoし、全てのデータの状態をk回操作を行った直後の状態に戻す。（ここでいう操作とは、結合、undo、出力のすべてである）
  • あるデータにおいて、そのビット列の、「連続する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
    J - 仕事をしよう！ (Working!)

    Time Limit: 7 sec / Memory Limit: 512 MB

    問題文

    joisinoお姉ちゃんは気がつくと家のテレビの前に座っていた。
    今まで夢でも見ていたのだろうか？
    ただテレビを見始めてから相当の時間がたっていたようで、壁にかかっている時計は仕事が始まる1時間前をさしていた。

    だが幸いなことにjoisinoお姉ちゃんが勤めている市役所は家からとても近い。
    というわけで悠々と職場に着いたjoisinoお姉ちゃんは、いきなり自分が道路整備課に配属されたことを知らされた。

    この市は今、都市開発がとても盛んでそれに伴う交通事情の悪化が懸念されている。
    そこで市はjoisinoお姉ちゃんに交通事情の把握を任せることにした。

    この市は今の時点では1つの都市が存在している。
    だがこれから都市開発によって都市の数が増えることが予想される。
    この市は新たに都市を作るときは、既存の都市を1つ選んで新しい都市との間に道を作る。
    よってすべての時において、都市の数をnとするとn-1本の道が存在している。
    また、はじめにあった都市は都市0と呼ばれ、i(1 ≦ i)番目に作られた都市は都市i、i(1 ≦ i)番目に作られた道は道iと呼ばれる。

    また、この市ではそれぞれの都市の人口も変化しているので、それぞれの道の所要時間も変化していく。
    それに加えて、住民の利便性の向上のためある都市から最も行くのに時間のかかる都市への所要時間を知る必要もある。

    このような状況の中でjoisinoお姉ちゃんには都市に関するクエリがQ個与えられる。
    i(1 ≦ i ≦ Q)番目の情報は次の3種類のどれかである。

    • クエリ1･･･都市が新しく作られ、その都市はA_iと所要時間C_iの道で結ばれた。
    • クエリ2･･･道A_iの所要時間がC_iに変わった。
    • クエリ3･･･都市A_iから最も行くのに時間のかかる都市への所要時間を知る必要がある。

    このうちクエリ3が来たときにはそれに答えないといけない。

    しかし、この仕事はとても厄介なので、手作業でやっていると職場で暮らすことになってしまう。
    そこでjoisinoお姉ちゃんはプログラムを組んでこの仕事を代わりにやってもらおうと思った。

    入力

    入力は以下の形式で標準入力から与えられる。

    Q
T_1 A_1 C_1
T_2 A_2 C_2
：
T_Q A_Q C_Q
    • 1行目には、クエリの数Q(1 ≦ Q ≦ 5*10^5)が与えられる
    • 2行目からのQ行のうちi行目にはi番目のクエリが書かれており、T_i(1 ≦ T_i ≦ 3),A_i(0 ≦ A_i ≦ 今ある都市の数-1),C_iが空白区切りで与えられる。
    • T_iはクエリの種類を表している。
    • T_i = 1のときは都市が新しく作られ、その都市は都市A_iと所要時間C_i(1 ≦ C_i ≦ 10^9)の道で結ばれたことを表している。
    • T_i = 2のときは道A_iの所要時間がC_i(1 ≦ C_i ≦ 10^9)に変わったことを表している。
    • T_i = 3のときは都市A_iから最も行くのに時間のかかる都市への所要時間を知る必要があることを表している。C_iは無視してよい。また、都市が1つしかない場合はこの答えは0となる。

    配点

    この問題には部分点がある。

    • データセット1は、Q ≦ 10^4を満たし、これに正解すると5点が得られる。
    • データセット2では追加の制約はなく、これに正解すると155点が得られる。

    出力

    出力はクエリ3の数だけ行数がある。
    i行目にはi個目のクエリ3に対する答えを出力せよ。
    出力の末尾にも改行を入れること。

    入力例1

    6
1 0 10
1 1 7
3 1 0
2 2 5
1 0 17
3 0 0

    出力例1

    10
17

    この場合、次のようなことが行われている。

    • クエリ1のタイプは1なので都市1が新たに作られ都市0と所要時間10の道で結ばれる。
    • クエリ2のタイプは1なので都市2が新たに作られ都市1と所要時間7の道で結ばれる。
    • クエリ3のタイプは3なので都市1から最も行くのに時間のかかる都市への所要時間を出力する。この場合は都市0へ行くときの10を出力する。
    • クエリ4のタイプは2なので道2の所要時間が5に変更される。
    • クエリ5のタイプは1なので都市3が新たに作られ都市0と所要時間17の道で結ばれる。
    • クエリ6のタイプは3なので都市0から最も行くのに時間のかかる都市への所要時間を出力する。この場合は都市3へ行くときの17を出力する。
    また、すべてのクエリを処理したとき都市は下の図のようになっている。

    入力例2

    7
3 0 0
1 0 10
2 1 15
1 0 7
1 2 5
1 2 8
3 0 0

    出力例2

    0
15

    この場合、次のようなことが行われている。

    • クエリ1のタイプは3なので都市0から最も行くのに時間のかかる都市への所要時間を出力する。この場合はほかに都市がないので0を出力する。
    • クエリ2のタイプは1なので都市1が新たに作られ都市0と所要時間10の道で結ばれる。
    • クエリ3のタイプは2なので道1の所要時間が15に変更される。
    • クエリ4のタイプは1なので都市2が新たに作られ都市0と所要時間7の道で結ばれる。
    • クエリ5のタイプは1なので都市3が新たに作られ都市2と所要時間5の道で結ばれる。
    • クエリ6のタイプは1なので都市4が新たに作られ都市2と所要時間8の道で結ばれる。
    • クエリ7のタイプは3なので都市0から最も行くのに時間のかかる都市への所要時間を出力する。この場合は都市1や都市4へ行くときの15を出力する。
    また、すべてのクエリを処理したとき都市は下の図のようになっている。

    入力例3

    10
1 0 234
1 1 354
2 1 145
2 1 456
2 1 51
3 0 0
1 0 352
3 0 0
2 1 234
3 3 0

    出力例3

    405
405
940