日本では防災研究が盛んに行われており，近年その重要性がますます増している． 避難経路の評価も重要な研究のひとつである． 今回は直線状の通路の安全評価を行う．

通路は W 個のユニットに分けられており，一方の端のユニットからもう一方の端のユニットまで 1,  2,  3,  … ,  W の番号がつけられている． 通路内の各ユニットには，入口の扉，出口の扉，防火扉のいずれか1つが存在する． 入口の扉，出口の扉，防火扉はそれぞれ通路内に複数個存在しうる．

この問題では時刻 t=0 で火災が発生したと想定する． それにより，通路の外部にいて避難しようとしている人々が入口の扉を通じて通路へ入り，より安全な場所へ出るために出口の扉へ脱出しようとするものとする． 避難中のそれぞれの人は単位時刻ごとに 1 つのユニットを移動するか，今のユニットに留まることができる． すなわち，時刻 t にある人がユニット i にいたとするとき，その人は時刻 t+1 ではユニット i-1,  i,   i+1 の3つの数字のうち 1 以上 W 以下であるものを選択し，その番号のユニットへ移動することができる． 防火扉があるユニットは，ある一定時刻以降になると完全に遮断されてしまい，避難中の人々はそのユニットに立ち入りできなくなる．また，そのユニット内に居た人々もそこから他のユニットに移動できなくなってしまう．

この問題における目的は，それぞれの扉の情報が与えられるので，避難中の人々が最適に行動した時に最大で何人が出口の扉へたどり着けるか計算することである．

通路の情報がW個の整数a_iで与えられる．

• a_i = 0のとき，i 番目のユニットが出口の扉であることをあらわす．
• a_i < 0のとき，i 番目のユニットが防火扉により時間 |a_i| 以降出入りできなくなることを表す．
• a_i > 0のとき，i 番目のユニットが入口の扉であることをあらわし，時刻 t=0, 1, 2, … , a_i-1 のそれぞれにおいて，ちょうど一人の人が i 番目のユニットに現れる．時刻 t に現れた人は，時刻 t+1 以降から移動を開始する．

出口の扉へたどり着ける最大の人数を求めよ．

W
a_1 a_2 ... a_W

入出力例

入力例 1

7
2 0 -2 3 2 -2 0

出力例 1

4

1,   4,   5番目のユニットに入口の扉があり， 2,   6番目のユニットに出口の扉がある．
1番目のユニットからは，2番目のユニットへ２人出ることができる．
4番目のユニットからは，2番目のユニットへ１人出ることができる．
5番目のユニットからは，7番目のユニットへ１人出ることができる．
よって合わせて４人が出口へとたどり着ける．

入力例 2

4
1 1 1 1

出力例 2

0

出口がないので誰も脱出できない．

入力例 3

9
10 -10 10 -10 10 -10 10 -10 0

出力例 3

24

あるところに銃の腕に自信をもつ猟師がいました． 猟師はある日，「ウィリアムテルというスイス人が，息子の頭にりんごを乗せて遠くから矢で撃ち落とすパフォーマンスで有名になった」というお話を聞きました． それを聞いて"自分のほうがもっと凄い!!"と思った猟師は動いている人の上にりんごを乗せて撃ちぬくパフォーマンスを考えつきました．

猟師は広場に N 人の人を集め，それぞれの人の上にりんごを乗せました． i 番目の人は時刻 t=0 のとき，座標 (x_i,  y_i) にいます． そこから速度ベクトル (u_i,  v_i) にしたがって歩きます． すなわち，時刻 t  ≥  0 のとき，i 番目の人は座標 (x_i + t \times u_i  ,   y_i + t \times v_i) にいます． ここで，人々は十分小さいので，同じ座標に複数の人がいたり，同じ座標ですれ違ったりできると仮定します．

猟師は人々を驚嘆させるために，一発の弾丸でできるだけ多くのりんごを撃ち落とすことにしました． 猟師は t ≥ 0 であるような任意の時刻に，任意の座標から任意の方向に向けて弾丸を放つことができます． 放たれた弾丸は無限の速さで直線軌道で移動し，りんごに当たった場合貫通して移動します． 弾丸を一発だけ打つとき，最大で何個のりんごを撃ち落とせるか計算してください．

N
x_1 y_1 u_1 v_1
...
x_N y_N u_N v_N

入出力例

入力例 1

5
0 0 0 0
1 0 -1 1
-1 0 1 -1
1 1 -1 1
-1 -1 1 -1

出力例 1

5

時刻１に５人がｙ軸上に並ぶので最大５つのりんごを撃ち落とせる．

入力例 2

5
0 0 0 0
1 0 1 0
-1 0 -1 0
1 1 1 1
-1 -1 -1 -1

出力例 2

3  

入力例 3

15
-10 9 2 1
2 10 0 -1
-10 -4 0 -3
-2 8 0 -1
0 -10 -1 -2
-8 5 0 -1
-7 -8 -3 1
10 -6 -2 -3
9 -6 1 0
10 -5 3 1
10 1 0 -3
-4 7 0 -1
10 -9 2 2
2 -5 -1 1
9 -10 3 1

出力例 3

5

ある学生は朝にいつも乗る通学バスで，あることに気がついた． そのバスの利用者がいつも同じなのだ． 気になってバスに乗っている利用者たちに聞いてみると，毎日決まった時刻にバス停に来ているようである． それなら，乗客にとってもっとよいバスの時間割があるのではないかとその学生は考えた．

学生の乗る通学路には，バスの営業所から終点までにS個のバス停が一直線に並んでいる．(営業所はバス停には含まれないが，終点はバス停に含まれる．) 各バス停には，営業所から近い方から順に1 から S までの番号が付けられている． 営業所と i 番目のバス停の距離は x_i である． バスはまず営業所を出発し，それから x_i 経った後に i 番目のバス停に到着する． バス停には N 人の利用者がやって来る． i 番目の利用者は時刻 t_i にバス停 p_i にやって来る．

この通学路には1日にちょうど M 本のバスが営業所から終点まで走ることになっている． バスはバス停に止まると，そのバス停で待っていた利用者を全員回収して，次のバス停に向かう． バス停で利用者を回収する時間は無視出来ると仮定する． いま各バスが営業所から出発する時刻を自由に決めることができるとき，利用者の待ち時間の和を最小化しよう．

S N M
x_1 ... x_S
t_1 p_1
...
t_N p_N

入出力例

入力例 1

2 2 1
1 5
0 1
0 2

出力例 1

4

入力例 2

2 3 2
1 15
0 1
5 1
5 2

出力例 2

5

入力例 3

4 8 1
6 38 105 390
14 1
4 2
39 3
89 2
32 4
1 1
25 1
60 4

出力例 3

1123

M 個の相異なるアルファベット var_1,  var_2,   … ,  var_M がある． 0,   1,   … ,   9,   var_1,   var_2,   … ,   var_M の 10+M 種類の文字からなる，長さ N の文字列 s_1s_2s_3…s_N が与えられる． この文字列における各アルファベットを数字で置き換えて回文になるようにしたい．(回文とは，前から読んでも後ろから読んでも同じ文字列をあらわす．) ここで，同じアルファベットは同じ数字で置き換えなければならない．また与えられたすべてのアルファベットvar_iは少なくとも，一度は文字列s_1s_2s_3…s_Nにあらわれる．

アルファベット var_i は 0 以上 u_i 以下の，leading zero を含まない整数に置き換える事ができる． 置き換えた後の文字列が回文になるような置き換え方が何通り存在するかを，mod 10^9+7 で求めよ． なお，アルファベットの置き換え方が異なれば，得られる文字列が同じでも異なるものとして数える．

N M
s_1s_2s_3…s_N
var_1 u_1
...
var_M u_M

入出力例

入力例 1

3 1
a1a
a 99

出力例 1

19

入力例 2

5 3
jbfjb
f 50
b 25
j 5

出力例 2

252

入力例 3

7 3
jag2013
j 53
a 10
g 93

出力例 3

23

不思議な生き物と人間が互いに助け合って生きている世界． この世界では自分で捕まえたモンスター同士を戦わせる大会が盛んに行われており， 多くの少年少女達が世界一のトレーナーを目指している．

大会では自分が捕まえたモンスターからパーティを作り，パーティ同士のバトルをする． モンスターのペアには相性があり，相性が非常に悪い場合と普通の場合がある． 相性が非常に悪い場合，そのペアのモンスターを同じパーティに入れることはできない． 相性が普通の場合には，友情度という数値で相性の良さが表現される． バトルでは，パーティ全体の友情度の和が勝負の鍵となる．

いまN匹のモンスターからK匹のモンスターからなるパーティを作りたい． M個のモンスターのペア(a_i,   b_i)に対して相性が分かっており，整数 c_i で表されている． c_i = 0 のとき，a_i 番目のモンスターと b_i 番目のモンスターは相性が非常に悪いことを意味する． c_i  ≠  0 のとき，a_i 番目のモンスターと b_i 番目のモンスターは相性が普通であり，その友情度は c_i であることを意味する． 与えられたM個のペア以外は，相性が普通であり，それらの友情度はすべて0である．

パーティの友情度の和を最大にする選び方を考えてみよう．

N M K
a_1 b_1 c_1
...
a_M b_M c_M

入出力例

入力例 1

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

出力例 1

4

入力例 2

3 1 3
1 2 -10

出力例 2

-10

入力例 3

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

出力例 3

Impossible

\{1,  2,  … ,  N\}の順列 (p(1),  p(2),  … ,  p(n)) が与えられる． (l_i,  r_i) からなるクエリが Q 個与えられるので，各クエリに対して以下の擬似コードによる処理結果を出力せよ．

1. ret   :=   0, (x(1),  x(2),  … ,  x(N))  :=  (1,  2,  … ,  N) とおく．
2. 各i   ∈ \{1,   2,  … ,   N\} について y(i) := p(x(i)) とする．
3. 各i   ∈ \{1,   2,  … ,   N\} について x(i)   =  y(i)とする．
4. ret   :=  ret + x(l_i) + x(l_i+1) + …  + x(r_i)
5. もし (x(l_i),  x(l_i+1),  … ,  x(r_i)) = (l_i,  l_i+1,  … ,  r_i) なら (ret mod 10^9+7) を出力して終了する．そうでないなら 処理２に戻る．

N Q
p(1) p(2) ... p(N)
l_1 r_1
...
l_Q r_Q

入出力例

入力例 1

5 2
5 1 2 3 4
1 1
2 4

出力例 1

15
45

擬似コード中の順列(x(1),   x(2),   … ,  x(N))は以下のように変化する．

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

入力例 2

10 5
3 1 2 5 4 10 6 7 9 8
1 10
1 5
3 3
5 10
9 10

出力例 2

660
90
6
178
67