레이팅 미적용JOI 商店には N 個の商品があり,商品には 1 から N までの番号が付けられている.
それぞれの商品には, 定価 と 種類 が定められている.商品 i ( \(1 \le i \le N\) ) の定価は P i 円である.商品の種類は 1 以上 M 以下の整数で表され,商品 i ( \(1 \le i \le N\) ) の種類は A i である.
JOI 商店は,セールを行うことにした.セールは M 日間続き, j 日目 ( \(1 \le j \le M\) ) には種類 j の商品をすべて定価の半額で買うことができる.
セールの期間中に, Q 人の客が JOI 商店を訪れた.客には 1 から Q までの番号が付けられている.客 k ( \(1 \le k \le Q\) ) はセールの T k 日目に JOI 商店を訪れ,商品 L k , L k +1, ..., R k を 1 つずつ買った.
セールの効果を調査するため,それぞれの客が商品を買うのにかかった金額を知りたい.
商品の情報と客の情報が与えられたとき,それぞれの客が商品を買うのにかかった金額を求めるプログラムを作成せよ.
1 ≦ N ≦ 200 000 .
1 ≦ M≦ 200 000 .
1 ≦ Q ≦ 200 000 .
2 ≦ P i ≦ 10 9 ( \(1 \le i \le N\) ).
P i は偶数である ( \(1 \le i \le N\) ).
1 ≦ A i ≦ M ( \(1 \le i \le N\) ).
1 ≦ T k ≦ M ( \(1 \le k \le Q\) ).
1 ≦ L k ≦ R k ≦ N ( \(1 \le k \le Q\) ).
入力される値はすべて整数である.
( 15 点) N ≦ 2 000 , M ≦ 2 000 , Q ≦ 2 000 .
( 20 点) M = 1 .
( 12 点) \(M \le 10\) .
( 14 点) A i ≠ A j ( \(1 \le i < j \le N\) ).
( 22 点) P i = 2 ( \(1 \le i \le N\) ).
( 17 点) 追加の制約はない.
入力は以下の形式で与えられる.
N M Q
P 1 A 1
P 2 A 2
...
P N A N
T 1 L 1 R 1
T 2 L 2 R 2
...
T Q L Q R Q
Q 行出力せよ. k 行目 ( \(1 \le k \le Q\) ) には,客 k が商品を買うのにかかった金額を,単位 (円) を省いて出力せよ.
5 1 3
10 1
40 1
30 1
20 1
50 1
1 2 4
1 3 5
1 1 5
45
50
75
5 3 3
10 1
40 3
30 2
20 1
50 3
1 2 4
3 3 5
2 1 5
80
75
135
5 5 3
50 2
70 4
20 5
30 1
10 3
4 2 4
5 1 5
2 3 4
85
170
50
10 5 4
2 1
2 5
2 4
2 3
2 4
2 2
2 2
2 4
2 2
2 1
3 2 7
1 1 7
2 1 10
5 5 8
11
13
17
8
10 10 10
741703628 7
231838922 5
920286164 3
763741914 5
246151406 7
54109256 1
966457488 5
441379880 10
458514202 2
224373612 1
5 5 10
2 2 7
1 9 9
1 3 4
9 4 6
1 1 7
9 4 7
4 8 8
7 5 9
1 4 5
1907757100
3182585150
458514202
1684028078
1064002576
3897234150
2030460064
441379880
2043536529
1009893320