A - 入社（Join the Company）

Time Limit: 1 sec / Memory Limit: 64 MB

問題文

joisinoお姉ちゃんは、AtJump社というゲーム会社に就職した。
joisinoお姉ちゃんは極めて優秀なプログラマーなので、ゲームプログラミングだけでなく、社内のいろいろな問題を解決するプログラムの作成も仕事として任されている。
joisinoお姉ちゃんの最初の仕事は、二つの文字列に分割されてしまった文字列を元に戻すプログラムを作成することである。

入力

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

S
T
  • 1行目には、分割された文字の前方の文字列S(1≦|S|≦50,Sはすべて小文字アルファベットからなる)が書かれている。
  • 2行目には、分割された文字の後方の文字列T(1≦|T|≦50,Tはすべて小文字アルファベットからなる)が書かれている。

出力

与えられた二つの文字列を順番通りつなげた文字列を1行に出力せよ。

入力例1

at
jump

出力例1

atjump

"at"と"jump"をつなげると、"atjump"になります

入力例2

joi
shino

出力例2

joishino
B - 書き換え（Rewrite）

Time Limit: 1 sec / Memory Limit: 64 MB

問題文

joisinoお姉ちゃんの次の仕事は、書類の書き換えである。
書類はN個あり、それぞれに、重要度と、書き換えるのにかかる時間が決まっている。
joisinoお姉ちゃんはどうしても定時に帰りたいので、あと作業できる時間はMしかない。
そこでjoisinoお姉ちゃんは、時間内に書き換える書類の重要度の合計の最大化したいと思い、その最大値を求めるプログラムを作ることにした。

入力

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

N M
V_1 T_1
V_2 T_2
:
V_N T_N
  • 1行目には、書類の個数を表す整数N(1≦N≦500)と残っている時間M(1≦M≦500)が書かれている。
  • 続くN行のうちi行目には、i番目の書類の重要度V_i(1≦V_i≦10^5)と書き換えにかかる時間T_i(1≦T_i≦500)が書かれている。

出力

時間内に書き換えられる書類の重要度の合計の最大値を、1行に出力せよ。

入力例1

3 3
1 2
6 1
4 1

出力例1

10

2番目と3番目の書類を書き換える。

入力例2

10 10
92231 7
70370 1
4423 10
96481 4
69142 2
91784 3
16328 3
85936 8
93166 2
17394 1

出力例2

351801
C - 有給休暇（Paid Vacation）

Time Limit: 1 sec / Memory Limit: 64 MB

問題文

joisinoお姉ちゃんは、大型連休が大好きである。
今、この先N日間が、休日かどうかの予定が決まっている。
また、joisinoお姉ちゃんはこの期間に、K回の有給休暇をもらうことができる。
言い換えれば、最大K日、休日でない日を休日に変えられる。
joisinoお姉ちゃんは、実現可能な、連続した休暇の日数の最大値が知りたいと思い、それを求めるプログラムを作ることにした。

入力

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

N K
H_1 H_2 .. H_N
  • 1行目には、この先の予定が決まっている日数N(1≦N≦10^5)と、有給休暇の数K(1≦K≦10^5)が与えられる。
  • 2行目には、N個1か0が空白区切りで並んでおり、左からi番目の数字は、i日目が休日なら1、そうでないなら0となっている。

出力

実現可能な、連続した休暇の日数の最大値を1行に出力せよ。

入力例1

6 2
1 0 1 0 0 1

出力例1

4

2日目と、4日目に有給休暇を取ればいい。

入力例2

10 1
1 1 0 0 1 1 1 0 1 1

出力例2

6
D - エンブレム（Emblem）

Time Limit: 1 sec / Memory Limit: 64 MB

問題文

joisinoお姉ちゃんの次の仕事は、デザイナーさんを助けることである。
今、あるエンブレムのデザインが行われている。
エンブレムは、以下の手順で作られる。

  • まず、縦H×横Wの大きさの長方形を用意する。
  • この時、左下の角を座標(0,0)とし、そこから右にx、上にy進んだ位置を座標(x,y)で表す。
  • 座標(0,0)から、座標(K,H) (1≦K＜W,Kは整数）に向かい、直線を引き始める。
  • 以後、以下のような動作を続ける。
  • 直線がどこかの角にぶつかるならば、そこでデザインを終了する。
  • 直線が角でない端にぶつかるならば、そこで、入射角と反射角が等しくなるように反射する。

    • たとえば、H=3,W=5,K=2のとき、図のようなデザインが完成する。ここで、赤い線が引いた線であり、濃い緑の線は、長方形の大きさをわかりやすくするために書いてあるだけなので、デザインには関係ない。

    こうしてできたデザインの美しさは、長方形の内部にある線の交点の個数と等しい。例えば、上の図であれば、赤い線が交わる点が2箇所あるので、美しさは2である。
    デザイナーさんは、H,W,Kの候補を考えたが、実際に描く前に、それを元に作ったデザインの美しさを前もって知っておきたいと思った。
    joisinoお姉ちゃんの仕事は、H,W,Kが与えられたときに、それを元に作ったデザインの美しさを求めるプログラムを作ることである。

    入力

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

    H W K
    • 1行目には、長方形の大きさを表す整数H(2 ≦ H ≦ 10^9),W(2 ≦ W ≦ 10^9)と、線を引く方向を示す整数K(1 ≦ K ＜ W)が与えられる。

    出力

    与えられたH,W,Kを元に作ったデザインの美しさを1行に出力せよ。

    入力例1

    3 5 2

    出力例1

    2

    この入力は、問題文中の図と対応している。

    入力例2

    7 6 5

    出力例2

    10

    入力例3

    1000000000 1000000000 999999999

    出力例3

    499999998500000001
    E - 歩くNPCたち（Walking NPCs）

    Time Limit: 3 sec / Memory Limit: 256 MB

    問題文

    joisinoお姉ちゃんの次の仕事は、ゲーム中のNPCの動きの確認である。
    左右に無限に伸びる直線上に、N人のNPCが立っている。
    また彼らは、ある一定の速度で決まった方向へ歩いている。
    直線上の一点を基準に、そこから右にx進んだ場所は、座標xで表される。
    ゲーム開始時、i番目のNPCは、座標X_iに立っており、また、１秒ごとに、V_iだけ移動する。
    より正確に言えば、ゲーム開始からt秒後に、i番目のNPCは、座標X_i+V_i×tの位置にいる。
    2人以上のNPCが、同時に同じ位置にいるかもしれない。
    これらのNPCの動きがゲームの仕様を満たしているかを確認するために、Q個の質問に答えなくてはならない。
    i番目の質問は、ゲーム開始からT_i秒後に、座標L_iと座標R_iの間にNPCは何人いるか、というものである。
    なお、座標L_iや座標R_iにいるNPCも、座標L_iと座標R_iの間にいるとみなす。
    joisinoお姉ちゃんの仕事は、これらの質問すべてに答えるプログラムを作ることである。

    入力

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

    N
X_1 V_1
X_2 V_2
:
X_N V_N
Q
T_1 L_1 R_1
T_2 L_2 R_2
:
T_Q L_Q R_Q
    • 1行目には、NPCの数を表す整数N(1 ≦ N ≦ 10^5)が与えられる。
    • 続くN行のうちi行目には、i番目のNPCの、初期位置X_i(0≦X_i≦10^5)と、符号付きの移動速度V_i(-10^5≦V_i≦10^5)が与えられる。
    • 次の１行には、質問の個数を表す整数Q(1≦Q≦10^5)が与えられる。
    • 続くQ行のうちi行目には、質問の内容を示す整数T_i(0≦T_i≦10^5),L_i(0≦L_i≦10^5),R_i(L_i≦R_i≦10^5)が与えられる。

    出力

    出力はQ行からなる。
    i行目には、i番目の質問に対する答えを出力せよ。

    入力例1

    3
4 1
8 -3
1 2
4
1 3 4
3 0 10
2 2 6
0 1 5

    出力例1

    1
2
3
2

    0～3秒後の、NPCの位置は、以下の図の通りである。

    入力例2

    4
0 50000
100000 -50000
0 2
100000 -3
6
0 50000 50000
1 50000 50000
2 50000 50000
20000 40000 40000
20001 39998 40001
20001 39997 40002

    出力例2

    0
2
0
2
0
2

    入力例3

    10
67812 -965
1766 93025
25587 -3294
14569 22
8830 203
50857 7
23407 -836
82660 80780
89781 1
86061 -1
10
97289 65405 94453
49386 73492 97497
75412 82840 94438
93076 43725 95471
18439 76630 93787
373 51319 92018
65554 30886 93533
66039 14298 95837
68359 90674 98196
31448 31879 98393

    出力例3

    0
0
0
0
0
4
0
1
0
1
    F - NPCの家 (NPC's House)

    Time Limit: 1 sec / Memory Limit: 256 MB

    問題文

    NPCの動きを確認したjoisinoお姉ちゃんは、今度はNPCの家の配置を任された。
    左右に無限に伸びる直線上に、N人のNPCが立っている。
    そして、その直線上にM軒のNPCの家を設置する。
    そして、各NPCは自分に最も近い家へと戻ることになる。

    このゲームでは、NPCの家は、リアリティーを追求するために、各NPCが家に戻るまでの距離の合計を最小化する位置に家を設置しなければならない。
    この作業を効率よくすすめるため、joisinoお姉ちゃんは各NPCが家に戻るまでの距離の合計の最小値を求めるプログラムを書くことにした。

    入力

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

    N M
X_1
X_2
：
X_N
    • 1行目には、NPCの数N、設置する家の数Mが与えられる。(1 ≦ N ≦ 1000, 1 ≦ M ≦ 1000)
    • 次のN行のうちi行目には、X_iが与えられ、i番目のNPCの位置を表している。(-10^9 ≦ X_i ≦ 10^9)

    配点

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

    • データセット1は、N ≦ 300, M ≦ 300を満たし、正解すると10点を得られる。
    • データセット2では追加の制約はなく、正解すると110点を得られる。

    出力

    各NPCが家に戻るまでの距離の合計の最小値を出力せよ。

    入力例1

    5 2
-3
-1
0
2
5

    出力例1

    6

    • 例えば、-1, 2の位置に家をおいた時、NPC1, 2, 3は-1の位置の家に戻り、NPC4, 5は2の位置の家へ戻るので、各NPCが家に戻るまでの距離の合計は2 + 0 + 1 + 0 + 3 = 6となる。
    • そして、これよりも各NPCが家に戻るまでの距離の合計を小さくする配置はないため、6が答えとなる。

    入力例2

    10 3
-3
12
-92
-45
-15
27
14
94
-39
75

    出力例2

    131
    G - 貢物（Tribute）

    Time Limit: 2.5 sec / Memory Limit: 256 MB

    問題文

    joisinoお姉ちゃんの次の仕事は、ゲームのテストプレイである。
    このゲームでは、主人公は情報を得るために、様々な村を訪れる。
    村人から情報を得るには、適切に貢ぎ物をいくつか選び、村に捧げなくてはならない（ここで、0個の貢物を捧げても、すなわち何も捧げなくてもよい）。
    貢ぎ物の種類はN種類あり、1～Nの番号がつけられている。
    また、村はM個あり、1～Mの番号がつけられている。
    そして、それぞれの村には、貢ぎ物に関する掟がある。
    二つ以上の村が、同じ掟を持つことはない。
    この掟は、ある二つの「条件」を同時に満たしてはならないと言うものである。
    「条件」とは、「ある貢ぎ物Xを捧げる」、もしくは、「ある貢ぎ物Xを捧げない」、というものである。
    さらに、ストーリーが進行するに連れ、村の合併が行われる。
    i回目の合併では、村P_iと村Q_iが合併し、村M+iになる。
    合併の際には必ず、村P_iと村Q_iが存在することが保証され、また合併のあとは、村P_iと村Q_iは消滅する。
    この時、新しくできた村には、合併元の村の掟がすべて残る。
    村の合併は、存在する村が村2M-1の一つになるまで行われる。
    村1〜村Mには、掟をすべて守る貢物の組み合わせが存在するが、村M+1〜村2M-1では、掟が互いに矛盾し、掟をすべて守るような貢物の組み合わせが存在しないかもしれない。
    joisinoお姉ちゃんの仕事は、村M+1〜村2M-1について、掟をすべて守るような貢物の組み合わせがあるかどうかを判定するプログラムを作ることである。

    入力

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

    N M
A_1 B_1
A_2 B_2
:
A_M B_M
P_1 Q_1
P_2 Q_2
:
P_{M-1} Q_{M-1}
    • 1行目には、貢物の種類の数を表す整数N(1 ≦ N ≦ 10^5)と、村の数を表す整数M(2 ≦ M ≦ 10^5)が与えられる。
    • 続くM行のうちi行目には、i番目の村の掟を表す整数。A_i(1≦|A_i|≦N),B_i(1≦|B_i|≦N)(|A_i|≠|B_i|)が与えられる。
    • ここで、A_i,B_iはそれぞれ、「条件」を表しており、A_i,B_i２つの条件を同時に満たしてはならないというのが、村iの掟である。
    • A_iが正のときは、貢物|A_i|を捧げるという条件を表しており、A_iが負のときは、貢物|A_i|を捧げないという条件を表している。B_iについても同様である。
    • 続くM-1行のうちi行目には、合併する村を示す整数P_i(1≦P_i＜M+i),Q_i(1≦Q_i＜M+i)が与えられる。

    配点

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

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

    • 出力

    出力はM-1行からなる。
    i行目には、村M+iについて、掟をすべて守るような貢物の組み合わせがある場合は"Possible"、ない場合は"Impossible"と出力せよ。

    入力例1

    3 4
1 2
-2 -3
-1 3
1 -2
1 3
2 5
6 4

    出力例1

    Possible
Possible
Possible

    例えば、村5には何も捧げないことができ、村6には｛貢物1と貢物3｝を捧げることができ、村7には｛貢物2｝を捧げることができる。

    入力例2

    3 4
-1 -2
2 3
1 -2
2 -3
1 4
2 5
6 3

    出力例2

    Possible
Possible
Impossible

    入力例3

    4 20
3 -2
4 -3
3 -1
-2 -3
-1 2
2 -4
2 -3
4 -1
1 4
-1 -3
4 2
1 -3
-2 -1
2 3
3 -4
-4 -2
-4 1
-1 -4
2 1
-4 -3
1 11
16 2
6 20
8 12
22 15
18 5
23 7
9 10
13 26
19 21
4 3
28 31
14 24
27 30
29 25
17 34
36 32
35 33
37 38

    出力例3

    Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Impossible
Possible
Impossible
    H - デバッグ（Debug）

    Time Limit: 2.5 sec / Memory Limit: 256 MB

    問題文

    joisinoお姉ちゃんの次の仕事は、デバッガーを助けることである。
    デバッガーは、先ほどあるバグを発見したのだが、再現する詳しい条件を忘れてしまった。
    そこで、覚えている条件にあう方法をすべて試そうと考えている。

    条件は、以下のとおりである。

  • このゲームにはN個の村と、M個の、異なる二つの村をつなぐ双方向に通行可能な道がある。これらの道を通らずに、ある村から別の村へ行く方法はない。
  • 村には1〜Nの番号がついており、また、どの二つの村についても、その間を直接結ぶ道の個数は1個以下である。
  • バグが再現した時は、ある村からスタートし、そこから4回、違う村へと移動していた。
  • この時、同じ村を2度以上通ることはなかった。

    • デバッグの時間を見積もるため、すべての村について、最初にその村にいた場合、考えられる移動経路が何通りあるかを知りたい。
    joisinoお姉ちゃんの仕事は、すべての村について、最初にその村にいた場合、考えられる移動経路が何通りあるかを求めるプログラムを作ることである。

    入力

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

    N M
A_1 B_1
A_2 B_2
:
A_M B_M
    • 1行目には、村の数を表す整数N(1 ≦ N ≦ 10^5)と、道の数を表す整数M(1 ≦ M ≦ 10^5)が与えられる。
    • 続くM行のうちi行目には、整数A_i(1≦A_i≦N),B_i(1≦B_i≦N)が書かれており、これは、i本目の道が、村A_iと村B_iを直接つないでいることを表す。

    配点

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

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

    • 出力

    出力はN行からなる。
    i行目には、最初に村iにいた場合、考えられる移動経路が何通りあるかを出力せよ。

    入力例1

    6 8
1 2
2 3
5 2
1 5
3 4
5 3
5 6
5 4

    出力例1

    7
4
4
7
2
4

    例えば、最初村1にいた場合には、以下の7通りの移動経路が考えられる。

  • 1→2→3→4→5
  • 1→2→3→5→4
  • 1→2→3→5→6
  • 1→2→5→3→4
  • 1→2→5→4→3
  • 1→5→2→3→4
  • 1→5→4→3→2

    • 入力例2

    6 15
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6

    出力例2

    120
120
120
120
120
120

    入力例3

    8 11
3 6
7 8
8 5
4 5
2 1
2 6
3 2
4 3
5 3
6 5
7 6

    出力例3

    12
14
11
17
11
9
15
17
    I - ボス（Boss）

    Time Limit: 2.5 sec / Memory Limit: 256 MB

    問題文

    joisinoお姉ちゃんの次の仕事は、ボス戦の難易度調整である。
    このボスの体は、細胞がマス目のように並んでおり、最も左上の細胞から右にx,下にy進んだ位置にある細胞は、座標(x,y)で表される。
    このボスとの戦いの最中に、N回のイベントが起こる。イベントは以下の3種類のうちいずれかである

  • イベント1
  • ある整数L,Rが与えられる。これがK回目のイベント1だとすると、y座標がK-1で、x座標がLからRまでの間にある細胞が弱体化する。
  • イベント2
  • ある整数Kが与えられ、y座標Kの細胞の弱体化が解除される。この時、必ずy座標Kに、弱体化している細胞があることが保証される。
  • イベント3
  • ある整数L,Rが与えられ、あなたには、ボスへの攻撃のチャンスが一回与えられる。
  • 弱体化した部分のあるy座標Kを選び、そこにある弱体化した細胞が、x座標AからBまでだったとすると、A＜LかつR＜Bのときのみ、この部分に対して攻撃が行える。
  • そして攻撃を行うと、(L-A)×(B-R)のダメージをボスに与えることができる。

    • 難易度調節のために、すべてのイベント3において、ボスに与えることのできる最大ダメージをあらかじめ知っておきたい。
    joisinoお姉ちゃんの仕事は、すべてのイベント3において、ボスに与えることのできる最大ダメージを求めるプログラムを作ることである。

    入力

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

    N
:
    • 1行目には、これから起こるイベントの数を表す整数N(1 ≦ N ≦ 2×10^5)が与えられる。
    • 続くN行のうちi行目には、i番目に起こるイベントの情報が書かれている。
    • 各行の先頭には、イベントの種類を表す整数T_i(1≦T_i≦3)が与えられる。
    • T_iが1のとき、その後に整数L_i(0≦L_i≦10^9),R_i(L_i≦R_i≦10^9)が与えられ、これがK回目のイベント1だとすると、y座標がK-1で、x座標がL_iからR_iまでの間にある細胞が弱体化することを意味する。
    • T_iが2のとき、その後に整数K_iが与えられ、y座標K_iの細胞の弱体化が解除されることを意味する
    • T_iが3のとき、その後に整数L_i(0≦L_i≦10^9),R_i(L_i≦R_i≦10^9)が与えられ、ボスへの攻撃のチャンスが一回あることを意味する。

    配点

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

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

    • 出力

    すべてのイベント3について、ボスに与えることのできる最大ダメージを1行に出力せよ。
    もし、どのy座標に対しても攻撃できない場合は、-1を出力せよ。

    入力例1

    9
1 0 10
1 2 12
3 5 5
3 8 9
2 0
3 5 5
3 8 9
2 1
3 5 5

    出力例1

    25
18
21
18
-1

  • 最初の2回のイベントでの弱体化のあと、ボスの状態は下の図のようになっている（弱体化した部分は赤で表されている）。
  • 次のイベントの攻撃のチャンスでは、y座標0を攻撃すると、(5-0)×(10-5)=25のダメージが与えられる。
  • 次のイベントの攻撃のチャンスでは、y座標1を攻撃すると、(8-2)×(12-9)=18のダメージが与えられる。
  • 次のイベントの弱体化解除で、ボスの状態は下の図のようになる。
  • 次のイベントの攻撃のチャンスでは、y座標1を攻撃すると、(5-2)×(12-5)=21のダメージが与えられる。
  • 次のイベントの攻撃のチャンスでは、y座標1を攻撃すると、(8-2)×(12-9)=18のダメージが与えられる。
  • 次のイベントの弱体化解除で、ボスの状態は下の図のようになる。
  • 次のイベントの攻撃のチャンスでは、攻撃できるy座標がないため、-1を出力する。

    • 入力例2

    7
1 3 7
1 0 6
1 4 10
3 1 3
3 6 7
3 5 5
3 4 6

    出力例2

    3
6
5
1

    入力例3

    20
3 268323303 605806817
3 397106901 526645597
1 242167025 963419065
3 306157656 666722488
3 90905255 723611215
1 135062270 656996756
1 72048580 708895403
1 254360876 741288738
3 353173849 652094091
3 274378199 520888695
1 128877839 722596185
3 367349293 905356554
3 336742409 649201453
1 353239854 521572577
2 3
3 5185803 799351855
1 139746807 783110900
3 375190636 656724546
1 462675641 992773167
1 77055484 555060299

    出力例3

    -1
-1
18985801177770087
-1
34559196595622576
38039325599084252
7268396812754948
29717251314463008
-1
40797612391288109
    J - 次のお仕事 (New Game)

    Time Limit: 7.5 sec / Memory Limit: 256 MB

    ※この問題は時間制限が長いので、テストケースに入出力例を入れていません。

    問題文

    ひとまずゲーム作りを終えたjoisinoお姉ちゃんは、次のゲームの企画をすることになった。
    そして、今度は地形が変わるマップでのアドベンチャーゲームを作ろうと思った。
    以下joisinoお姉ちゃんの考えである。

    このゲームではN個の街があって、それがN-1本の双方向に通行可能な道で互いに行き来できるようにつながっていることにしよう。
    やっぱりアドベンチャーゲームなら街を巡ってゴールを目指すのがいいかな。
    今回は遠回りすることは考えなくていいか。
    それで、地形が変わるならやっぱり標高が重要かな。
    標高が高い街を通るとレアなアイテムがもらえるとかどうだろう？
    それなら旅で通る街の標高の最大値を求めればいいかな？
    地形を変えるならある街から道をc本以下たどることでたどり着ける街すべての標高を変えるとかだね。

    整理すると、この2つのイベントを処理すればいいってことだよね。

    • イベント1
      整数a, b, cが与えられる。
      街aからb本以下の道でたどり着ける街の標高がcになる。
    • イベント2
      整数a, bが与えられる。
      街aから街bまでの最短経路の街の標高の最大値に応じてアイテムがもらえる。

    でも、これだとどれぐらいのアイテムをもらえるんだろう？

    そこでjoisinoお姉ちゃんは、イベント2において最短経路の街の標高の最大値を求めるプログラムを書くことにした。

    入力

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

    N Q
E_1
E_2
：
E_N
S_1 G_1
S_2 G_2
：
S_{N-1} G_{N-1}
T_1 A_1 B_1 C_1
T_2 A_2 B_2 C_2
：
T_Q A_Q B_Q C_Q
    • 1行目には、街の数N、イベントの数Qが与えられる。(1 ≦ N ≦ 70000, 1 ≦ Q ≦ 70000)
    • 次のN行のうちi行目には、E_iが与えられ、街iのはじめの標高を表している。(1 ≦ E_i ≦ 10^9)
    • 次のN-1行のうちi行目には、S_i,G_iが与えられ、S_iとG_iが道で結ばれていることを表す。(1 ≦ S_i, G_i ≦ N, S_i ≠ G_i)
    • 次のQ行のうちi行目には、T_i, A_i, B_i, C_iが与えられる。
    • T_i=1の時、イベント1を表し、街A_iからB_i本以下の道でたどり着ける街の標高がC_iになる。(1 ≦ A_i ≦ N, 0 ≦ B_i ≦ 10^9, 1 ≦ C_i ≦ 10^9)
    • T_i=2の時、イベント2を表し、街A_iから街B_iまでの最短経路の街の標高の最大値を出力する。(1 ≦ A_i, B_i ≦ N)
      A_i = B_iの場合は街A_iの標高を出力する。 また、C_iは無視して構わない。

    出力

    すべてのイベント2について、最短経路の街の標高の最大値を出力せよ。

    入力例1

    5 5
3
2
5
2
6
1 2
2 3
3 5
3 4
2 1 5 0
1 4 1 7
2 5 2 0
1 3 1 2
2 4 1 0

    出力例1

    6
7
3

    • クエリ1 : 街1から街5までの最短経路で通る街は1, 2, 3, 5なので、それらの標高3, 2, 5, 6の最大値6を出力する。
    • クエリ2 : 街4から1本の道を通ってたどり着ける街は4, 3なので、それらの標高を7にする。
    • クエリ3 : 街5から街2までの最短経路で通る街は5, 3, 2なので、それらの標高6, 7, 2の最大値7を出力する。
    • クエリ4 : 街3から1本の道を通ってたどり着ける街は3, 2, 4, 5なので、それらの標高を2にする。
    • クエリ5 : 街4から街1までの最短経路で通る街は4, 3, 2, 1なので、それらの標高2, 2, 2, 3の最大値3を出力する。

    入力例2

    10 10
78
87
33
57
93
49
45
17
56
44
1 2
2 3
1 4
1 5
4 6
3 7
6 8
3 9
6 10
2 2 2 0
1 1 2 59
1 7 1 96
2 7 8 0
2 3 4 0
2 10 4 0
1 8 2 45
1 3 3 24
2 2 1 0
2 6 9 0

    出力例2

    87
96
96
59
24
45