问题描述

JOI 商店有若干商品，商品编号从 1 到 N。

商品 i 的标价为 Pi 日元，商品类型由整数表示，商品 i 的类型为 Ai。

JOI 商店决定举办为期一天的促销活动，在这一天（第 j 天）可以以标价的一半购买所有类型为 j 的商品。

促销期间，有编号从 1 到 Q 的顾客光临 JOI 商店。顾客 k 在促销当天到 JOI 商店购买从 Lk 到 Rk 的商品。

为了调查促销活动的效果，我们想知道每个顾客购买商品花费了多少钱。

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

约束条件

• 1 ≤ N ≤ 200,000
• 1 ≤ M ≤ 200,000
• 1 ≤ Q ≤ 200,000
• 2 ≤ Pi ≤ 10^9（1 ≤ i ≤ N），Pi 是偶数
• 1 ≤ Ai ≤ M（1 ≤ i ≤ N）
• 1 ≤ Tk ≤ M（1 ≤ k ≤ Q）
• 1 ≤ Lk ≤ Rk ≤ N（1 ≤ k ≤ Q）
• 所有输入值均为整数

输入

输入格式如下：

N M Q
P1 A1
P2 A2
...
PN AN
T1 L1 R1
T2 L2 R2
...
TQ LQ RQ

输出

输出 Q 行。在第 k 行输出顾客购买商品花费的金额，省略单位（日元）。

输入示例 1

5 1 3
10 1
40 1
30 1
20 1
50 1
1 2 4
1 3 5
1 1 5

输出示例 1

45
50
75

输入示例 2

5 3 3
10 1
40 3
30 2
20 1
50 3
1 2 4
3 3 5
2 1 5

输出示例 2

80
75
135

输入示例 3

5 5 3
50 2
70 4
20 5
30 1
10 3
4 2 4
5 1 5
2 3 4

输出示例 3

85
170
50

输入示例 4

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

输出示例 4

11
13
17
8

输入示例 5

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

输出示例 5

1907757100
3182585150
458514202
1684028078
1064002576
3897234150
2030460064
441379880
2043536529
1009893320