あなたは Juicy Orange Industry 社を知っているだろうか? この会社の業務は美味しいオレンジを栽培して出荷することである．ここでは略して JOI 社と呼ぶ．

JOI 社では，収穫された N 個のオレンジを箱詰めして出荷することになった．オレンジは工場にあるベルトコンベアの上に並べられており，ベルトコンベアの前から順番に 1 から N までの番号が付けられている．オレンジは大小さまざまであり，オレンジ i (1 \leqq i \leqq N) の大きさは A_i である．

これらのオレンジを前から順番にいくつかの箱に分けて詰める．ひとつの箱には連続した番号のオレンジしか詰めることができない．

ひとつの箱には最大で M 個までのオレンジを詰めることができる．ある箱にいくつかのオレンジを詰めるためにかかるコストは，箱に詰める最大のオレンジの大きさを a，箱に詰める最小のオレンジの大きさを b，箱に詰めるオレンジの個数を s としたときに，K + s \times (a - b) で求めることができる．ここで，K は箱にかかるコストであり，すべての箱で共通の値である．

適切な個数の箱を用意して，すべてのオレンジを適切に箱詰めすることで，箱詰めにかかるコストの総和をできるだけ小さくしたい．

課題

ベルトコンベア上に並んでいるオレンジの情報と，ひとつの箱に詰められるオレンジの個数の最大値および，箱にかかるコストが与えられたとき，箱詰めにかかるコストの総和の最小値を求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 1 \leqq N \leqq 20\,000．
• 1 \leqq M \leqq 1\,000．
• 0 \leqq K \leqq 1\,000\,000\,000．
• 1 \leqq A_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．
• M \leqq N．

小課題

小課題 1 [20 点]

• N \leqq 20 を満たす．

小課題 2 [50 点]

以下の条件を満たす．

• N \leqq 2\,000．
• M \leqq 100．

小課題 3 [30 点]

追加の制限はない．

入力例 1

6 3 6
1
2
3
1
2
1

出力例 1

21

1 番目の箱にオレンジ 1 からオレンジ 3 までの 3 個のオレンジを詰め，2 番目の箱にオレンジ 4 からオレンジ 6 までの 3 個のオレンジを詰めると，箱詰めにかかるコストの総和は (6 + 3 \times (3 - 1)) + (6 + 3 \times (2 - 1)) = 21 となる．

どのように詰めても箱詰めにかかるコストの総和が 21 を下回ることはないので，21 を出力する．

入力例 2

16 4 12
3
10
13
10
19
9
12
16
11
2
19
9
13
2
13
19

出力例 2

164

11 個の箱を用意して，それぞれの箱に前から順に 1 個，3 個，1 個，1 個，3 個，1 個，1 個，2 個，1 個，1 個，1 個のオレンジを詰めることで，箱詰めにかかるコストの総和が最小となる．

入力例 3

16 6 14
19
7
2
15
17
7
14
12
3
14
5
10
17
20
19
12

出力例 3

177

入力例 4

10 1 1000000000
1
1
1
1
1
1
1
1
1
1

出力例 4

10000000000

答えが 32 ビット符号付き整数の範囲に収まるとは限らないことに注意せよ．

JOI 商店街には大通りに沿って N 個の店があり，JOI 商店街の入口から出口に向かってそれぞれ 1, 2, \ldots, N の番号が付けられている．JOI 商店街は一方通行で，入口から出口方向へしか移動することはできない．

まちおこしのため，JOI 商店街でスタンプラリーを行うことになった．このスタンプラリーでは，それぞれの店は J，O，I のいずれかのスタンプを用意し，店で買い物をした人はスタンプカードにスタンプを押してもらう．スタンプラリーに参加する人はちょうど 3 つの店に入る．商店街の入口では 3 つの欄のあるスタンプカードを配り，1 回目に入った店，2 回目に入った店，3 回目に入った店のスタンプを押してもらう．商店街の出口でスタンプカードを回収し，押されたスタンプが先に入った店のものから順に J，O，I になっているとき，出口で商品券がもらえるキャンペーンを実施することになった．押されたスタンプの種類や順番が異なるときは商品券はもらえない．

すでに N 個のすべての店はどのスタンプを用意するか決めたが，新たに 1 つの店を JOI 商店街に出すことになり，新しく出店する場所と，その店が用意するスタンプを決めることになった．新しい店を出す場所は，店 i と店 i + 1 の間 (1 \leqq i \leqq N - 1)，入口と店 1 の間，店 N と出口の間のいずれかから決める．また，新しい店のスタンプは J，O，I の 3 通りから決める．

商品券をもらえるような店の選び方の数が大きいほど，スタンプラリーが盛り上がると商店街は考えた．そこで，新しく出す店の場所と用意するスタンプを決めたときの，上記の店の選び方の数の最大値を求めたい．

課題

JOI 商店街のすでにある店が用意したスタンプの情報が与えられたとき，新しく出す店の場所と用意するスタンプを決めたときの，商品券をもらえるような店の選び方の数の最大値を求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 3 \leqq N \leqq 100\,000．

小課題

小課題 1 [30 点]

• N \leqq 200 を満たす．

小課題 2 [20 点]

• N \leqq 3\,000 を満たす．

小課題 3 [50 点]

追加の制限はない．

入力例 1

5
JOIOI

出力例 1

6

入力例 1 では，店 1 と店 2 の間に，スタンプ J を用意する新しい店を出したとき，店が用意したスタンプを入口から順に並べると JJOIOI となる．

このとき，商品券をもらえるような店の選び方は以下の 6 通りである．

• 1, 3, 4 番目の店に行く．
• 1, 3, 6 番目の店に行く．
• 1, 5, 6 番目の店に行く．
• 2, 3, 4 番目の店に行く．
• 2, 3, 6 番目の店に行く．
• 2, 5, 6 番目の店に行く．

入力例 1 において，商品券をもらえるような店の選び方が 7 通り以上になることはない．

入力例 2

7
JJJOIII

出力例 2

18

入力例 3

4
OIIJ

出力例 3

2

入力例 3 では，入口と店 1 の間にスタンプ J を用意する新しい店を出したとき，商品券をもらえるような店の選び方の数が最大となる．

JOI 国には N 個の都市があり，それぞれ 1, 2, \ldots, N の番号が付けられている．都市 1 は JOI 国の首都である．

また，JOI 国には鉄道会社がひとつだけあり，この会社は M 個の路線を運行している．これらの路線にはそれぞれ 1, 2, \ldots, M の番号が付けられており，i 番目 (1 \leqq i \leqq M) の路線は都市 U_i と都市 V_i を双方向に結んでいる．都市と都市の間を鉄道以外で移動することはできない．また，どの都市からどの都市へもいくつかの路線を乗り継いで移動することができるようになっている．

現在，どの路線の運賃も 1 円である．経営不振に陥った鉄道会社は，今後 Q 年間かけていくつかの路線の運賃を値上げする計画を立てた．この計画では，計画開始から j 年目 (1 \leqq j \leqq Q) の年初めに路線 R_j の運賃を 1 円から 2 円に値上げする予定である．値上げされた路線の運賃は，その後ずっと 2 円のままであり，再び値上げすることはない．

ところで，この鉄道会社では，毎年，各都市の住民の満足度調査を行っている．計画開始前は，どの都市の住民もこの鉄道会社に満足しているが，値上げによって不満を持つ住民が現れる可能性がある．

それぞれの年の満足度調査は，その年の値上げの実施後に行う．したがって，j 年目 (1 \leqq j \leqq Q) の満足度調査は，路線 R_1, R_2, \ldots, R_j の運賃の値上げは完了し，それ以外の路線の運賃は値上げされていない状態で行われることになる．j 年目 (1 \leqq j \leqq Q) の満足度調査では，都市 k (2 \leqq k \leqq N) の住民は，以下の条件が満たされるとき，そしてそのときに限り鉄道会社に不満を抱く．

• その時の運賃で都市 k から首都である都市 1 へ移動するときの費用の最小値が，計画開始前の運賃で都市 k から都市 1 へ移動するときの費用の最小値よりも大きい．

ただし，いくつかの路線を使って移動するときの費用は，それぞれの路線の運賃の合計である．また，都市 1 の住民が鉄道会社に対して不満を抱くことはない．値上げ後の運賃で最小の費用を達成する経路は，計画開始前の運賃で最小の費用を達成する経路と異なる可能性があることに注意せよ．

計画の実行に先立って，今後 Q 年間の住民の満足度調査それぞれにおいて，鉄道会社に不満を抱く住民がいる都市の数を計算しておきたい．

課題

JOI 国の鉄道路線の情報と，運賃の値上げ計画が与えられたとき，それぞれの満足度調査において鉄道会社に不満を抱く住民がいる都市の数を求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 2 \leqq N \leqq 100\,000．
• 1 \leqq Q \leqq M \leqq 200\,000．
• 1 \leqq U_i \leqq N (1 \leqq i \leqq M)．
• 1 \leqq V_i \leqq N (1 \leqq i \leqq M)．
• U_i \neq V_i (1 \leqq i \leqq M)．
• 1 \leqq R_j \leqq M (1 \leqq j \leqq Q)．
• R_j \neq R_k (1 \leqq j < k \leqq Q)．
• どの 2 つの都市についても，それらを直接結ぶ路線は 1 個以下である．
• どの都市についても，その都市から都市 1 までいくつかの路線を使って移動することができる．

小課題

小課題 1 [12 点]

以下の条件を満たす．

• N \leqq 100．
• M \leqq 4\,950．
• Q \leqq 30．

小課題 2 [14 点]

• Q \leqq 30 を満たす．

小課題 3 [35 点]

• 正しい出力に現れる整数は 50 種類以下である．

小課題 4 [39 点]

追加の制限はない．

入力例 1

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

出力例 1

0
2
2
4
4

この入力例では，計画開始前，及びそれぞれの満足度調査の時点でのそれぞれの都市から都市 1 への運賃は，以下の表のようになる．

例えば，3 年目の満足度調査では，都市 3 と都市 5 の住民が不満を抱くので，出力の 3 行目には 2 を出力する．

入力例 2

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

出力例 2

1
1
2
2
3
3

入力例 3

2 1 1
1 2
1

出力例 3

1

あなたは南北方向にとても長く伸びたたくさんの道路と，東西方向にとても長く伸びたたくさんの道路が交わった形をした街に住んでいる．隣り合う 2 つの南北方向の道路の間隔は 1 km である．また，隣り合う 2 つの東西方向の道路の間隔も 1 km である．

この街には市役所が 1 つある．市役所のある交差点を (0, 0) と表す．この街の交差点は 2 つの整数 i, j を用いて交差点 (i, j) と表される．すなわち，交差点 (i, j) とは，交差点 (0, 0) から東に i km (i < 0 のときは西に -i km)，北に j km (j < 0 のときは南に -j km) 進んだ位置の交差点を表す．

市役所ではジョイ君という名の 1 匹の犬を飼っている．ジョイ君は K 日間の散歩の計画を立てた．散歩の計画は以下の通りである．

• K 日のうち最初の日の朝にはジョイ君は交差点 (0, 0) にいる．ジョイ君は交差点 (0, 0) に印を付ける．(0, 0) 以外にはジョイ君が印を付けた交差点はない．
• K 日のそれぞれの日の昼に散歩を行う．1 日の散歩は N 回のステップからなる．各ステップでは交差点から隣の交差点へと移動し，移動先に印を付ける．ジョイ君がそれぞれの日の昼にどう移動するかは日によらず一定である．
• 昼の移動が終わった後は，現在いる交差点で次の日の朝まで寝る．市役所では K 日間の散歩によってできるジョイ君の縄張りについて話題になっている．4 つの交差点 (a, b), (a + 1, b), (a + 1, b + 1), (a, b + 1) のいずれにもジョイ君が 1 回以上印を付けているとき，4 つの交差点で囲まれた区画はジョイ君の縄張りに属する．

あなたは，ジョイ君の散歩計画から，ジョイ君の縄張りに属する区画の個数を計算するプログラムを作 成することとなった．

この街の道路はとても長く，また，南北方向にも東西方向にも十分たくさんの道路があるため，散歩の途中でジョイ君が道路の端や街の端に到達することはない．

課題

ジョイ君の散歩計画が与えられると，ジョイ君の縄張りに属する区画の個数を求めるプログラムを作成せよ．

制限

すべての入力データは以下の条件を満たす．

• 1 \leqq N \leqq 100\,000．
• 1 \leqq K \leqq 1\,000\,000\,000．

小課題

小課題 1 [5 点]

以下の条件を満たす．

• N \leqq 50．
• K = 1．

小課題 2 [10 点]

• K = 1 を満たす．

小課題 3 [23 点]

• N \leqq 50 を満たす．

小課題 4 [62 点]

追加の制限はない．

入力例 1

12 1
EENWSEEESWWS

出力例 1

3

この入力例では，散歩は 1 日間で行われる．1 日目にジョイ君は市役所から出発して下図のように移動する．

黒丸はジョイ君が印を付けた交差点，白丸はジョイ君が印を付けていない交差点，二重丸は市役所のある交差点，数字は各ステップを表す．

ジョイ君の移動経路

入力例 1 において，下図の斜線部分で示された 3 個の区画がジョイ君の縄張りに属する．

入力例 1 におけるジョイ君の縄張り

入力例 2

12 2
EENWSEEESWWS

出力例 2

7

入力例 2 では，散歩が 2 日間に渡り行われる．それぞれの日の移動経路は入力例 1 と同一である．散歩が完了したとき，下図の斜線部分で示された 7 個の区画がジョイ君の縄張りに属する．

入力例 2 におけるジョイ君の縄張り

入力例 2 は，小課題 1 および小課題 2 の制約を満たさないことに注意せよ．

入力例 3

7 1
ENNWNNE

出力例 3

0

入力例 3 では，ジョイ君の縄張りに属する区画は存在しない．

入力例 4

16 5
WSESSSWWWEEENNNW

出力例 4

21

入力例 4 は，小課題 1 および小課題 2 の制約を満たさないことに注意せよ．

遠い昔，IOI 文明という高度な文明が栄えていた．しかし，火山の噴火により，この高度な文明はついに滅んでしまった．IOI 文明は直線状の河川に沿って繁栄しており，IOI 文明が滅んだとき，その地表面は平らであった．IOI 文明の跡地は座標平面の x 軸と見なすことができる．y 軸は高さ方向を表す．すなわち，座標平面において，直線 y = 0 は地表を，領域 y > 0 は地上を，領域 y < 0 は地下を表す．また，IOI 文明が滅んだとき，a 年前 (a \geqq 0) の地層は，直線 y = -a の位置にあった．

IOI 文明が滅んだ後，IOI 文明の跡地では Q 回の地殻変動が起きた．i 回目 (1 \leqq i \leqq Q) の地殻変動は，位置 X_i，方向 D_i，変動の量 L_i で表される．D_i は 1 または 2 である．i 回目の地殻変動は以下のように起きる．

• 地層の移動が次のように起きる．
  • D_i = 1 のとき，断層が点 (X_i, 0) を通る傾き 1 の直線に沿って造られ，この直線より上の領域にある地層が，直線に沿って高さ L_i だけ移動する．すなわち，この直線より上の点 (x, y) は，点 (x + L_i, y + L_i) に移動する．
  • D_i = 2 のとき，断層が点 (X_i, 0) を通る傾き -1 の直線に沿って造られ，この直線より上の領域にある地層が，直線に沿って高さ L_i だけ移動する．すなわち，この直線より上の点 (x, y) は，点 (x - L_i, y + L_i) に移動する．
• そのすぐ後に，領域 y > 0 の地層が風化によってすべて消える．

時は変わり現代，考古学者の JOI 博士は IOI 文明の遺跡を発掘することにした．JOI 博士はどの位置の地表の地層が，IOI 文明が滅ぶ何年前の地層であるかを知りたい．どのような地殻変動が起きたかは分かっている．あなたの仕事は，JOI 博士にかわって，1 \leqq i \leqq N を満たす各整数 i について，点 (i - 1, 0) と点 (i, 0)の間の地表の地層が IOI 文明が滅ぶ何年前の地層であるかを求めることである．

課題

IOI 文明の跡地に起きたの情報が与えられたとき，すべての整数 i (1 \leqq i \leqq N) に対し，点 (i - 1, 0) と点 (i, 0) の間の地表の地層が IOI 文明が滅ぶ何年前の地層であるかを出力せよ．

制限

すべての入力データは以下の条件を満たす．

• 1 \leqq N \leqq 200\,000．
• 1 \leqq Q \leqq 200\,000．
• -1\,000\,000\,000 \leqq X_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq Q)．
• 1 \leqq D_i \leqq 2 (1 \leqq i \leqq Q)．
• 1 \leqq L_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq Q)．

小課題

小課題 1 [18 点]

以下の条件を満たす．

• N \leqq 100．
• Q \leqq 100．
• -100 \leqq X_i \leqq 100 (1 \leqq i \leqq Q)．
• L_i = 1 (1 \leqq i \leqq Q)．

小課題 2 [16 点]

以下の条件を満たす．

• N \leqq 3,000．
• Q \leqq 3,000．

小課題 3 [66 点]

追加の制限はない．

入力例 1

10 2
12 1 3
2 2 2

出力例 1

3
3
5
5
5
5
5
5
2
2

この入力例は，以下の図に対応する．

入力例 2

10 6
14 1 1
17 1 1
-6 2 1
3 2 1
4 1 1
0 2 1

出力例 2

5
5
4
5
5
5
5
5
4
4

この入力例は，小課題 1 の制約を満たす．

入力例 3

15 10
28 1 7
-24 2 1
1 1 1
8 1 1
6 2 1
20 1 3
12 2 2
-10 1 3
7 2 1
5 1 2

出力例 3

15
14
14
14
14
12
12
12
12
12
12
12
15
15
12