쇼핑 2

문제

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, \dots , R_{k}$ 를 하나씩 샀다.

세일의 효과를 조사하기 위해, 각 손님이 상품을 사는 데 든 금액을 알고 싶다.

상품의 정보와 손님의 정보가 주어졌을 때, 각 손님이 상품을 사는 데 든 금액을 구하는 프로그램을 작성하시오.

제한

• $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} \neq A_{j}$ ($1 \le i < j \le N$).
5. ($22$ 점) $P_{i} = 2$ ($1 \le i \le N$).
6. ($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$ 가 상품을 사는 데 든 금액을 단위 (엔) 를 생략하여 출력한다.

예제 입력 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

손님 $1$ 이 상품을 사는 데 든 금액은 $40 \div 2 + 30 \div 2 + 20 \div 2 = 45$ 엔이므로, $1$ 번째 줄에는 $45$ 를 출력한다.

손님 $2$ 가 상품을 사는 데 든 금액은 $30 \div 2 + 20 \div 2 + 50 \div 2 = 50$ 엔이므로, $2$ 번째 줄에는 $50$ 을 출력한다.

손님 $3$ 이 상품을 사는 데 든 금액은 $10 \div 2 + 40 \div 2 + 30 \div 2 + 20 \div 2 + 50 \div 2 = 75$ 엔이므로, $3$ 번째 줄에는 $75$ 를 출력한다.

이 예제는 서브태스크 $1,2,3,6$ 의 제약을 만족한다.

예제 입력 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

손님 $1$ 이 상품을 사는 데 든 금액은 $40 + 30 + 20 \div 2 = 80$ 엔이므로, $1$ 번째 줄에는 $80$ 을 출력한다.

손님 $2$ 가 상품을 사는 데 든 금액은 $30 + 20 + 50 \div 2 = 75$ 엔이므로, $2$ 번째 줄에는 $75$ 를 출력한다.

손님 $3$ 이 상품을 사는 데 든 금액은 $10 + 40 + 30 \div 2 + 20 + 50 = 135$ 엔이므로, $3$ 번째 줄에는 $135$ 를 출력한다.

이 예제는 서브태스크 $1,3,6$ 의 제약을 만족한다.

예제 입력 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

이 예제는 서브태스크 $1,3,4,6$ 의 제약을 만족한다.

예제 입력 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

이 예제는 서브태스크 $1,3,5,6$ 의 제약을 만족한다.

예제 입력 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

이 예제는 서브태스크 $1,3,6$ 의 제약을 만족한다.