该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

商店有 $n$ 件商品，每件商品被编号为从 $1$ 到 $n$。

每件商品都有一个定价和种类。

• 商品 $i$（$1 \le i \le n$）的定价为 $p_i$ 元。

• 商品的种类用 $1$ 到 $m$ 之间的整数表示，商品 $i$（$1 \le i \le n$）的种类为 $a_i$。

商店决定举行一次促销活动。促销持续 $m$ 天，在第 $j$ 天（$1 \le j \le m$），所有种类为 $j$ 的商品均以定价的一半价格出售。

在促销期间，共有 $q$ 位顾客访问了商店。每位顾客被编号为从 $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 分）无额外约束。