题目描述

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$ 天访问商店，并购买了商品 $L_k, L_k+1, \cdots, R_k$ 各一件。

为了评估促销的效果，商店希望知道每位顾客购买商品所花费的金额。

给定商品信息和顾客信息，编写一个程序，计算每位顾客购买商品所花费的金额。

输入格式

输入以如下格式给出：

$N\ M\ Q$

$P_1\ A_1$

$P_2\ A_2$

$\vdots$

$P_N\ A_N$

$T_1\ L_1\ R_1$

$T_2\ L_2\ R_2$

$\vdots$

$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

提示

样例 1 解释

顾客 1 购买商品所花费的金额为 $40 \div 2 + 30 \div 2 + 20 \div 2 = 45$ 日元，因此第一行输出 45。

顾客 2 购买商品所花费的金额为 $30 \div 2 + 20 \div 2 + 50 \div 2 = 50$ 日元，因此第二行输出 50。

顾客 3 购买商品所花费的金额为 $10 \div 2 + 40 \div 2 + 30 \div 2 + 20 \div 2 + 50 \div 2 = 75$ 日元，因此第三行输出 75。

该输入样例满足子任务 1、2、3、6 的约束。

样例 2 解释

顾客 1 购买商品所花费的金额为 $40 + 30 + 20 \div 2 = 80$ 日元，因此第一行输出 80。

顾客 2 购买商品所花费的金额为 $30 + 20 + 50 \div 2 = 75$ 日元，因此第二行输出 75。

顾客 3 购买商品所花费的金额为 $10 + 40 + 30 \div 2 + 20 + 50 = 135$ 日元，因此第三行输出 135。

该输入样例满足子任务 1、3、6 的约束。

数据范围

• $1 \le N \le 200\,000$。
• $1 \le M \le 200\,000$。
• $1 \le Q \le 200\,000$。
• $2 \le P_i \le 10^9$（$1 \le i \le N$）。
• $P_i$ 为偶数（$1 \le i \le N$）。
• $1 \le A_i \le M$（$1 \le i \le N$）。
• $1 \le T_k \le M$（$1 \le k \le Q$）。
• $1 \le L_k \le R_k \le N$（$1 \le k \le Q$）。
• 所有输入的值均为整数。

子任务

1. （15 分）$N \le 2\,000$，$M \le 2\,000$，$Q \le 2\,000$。
2. （20 分）$M = 1$。
3. （12 分）$M \le 10$。
4. （14 分）$A_i \ne A_j$（$1 \le i < j \le N$）。
5. （22 分）$P_i = 2$（$1 \le i \le N$）。
6. （17 分）无额外约束。

翻译由 Qwen3-235B 完成。