Page not loading? Try clicking here.
Placeholder

#2142

[초등부] 2024 KOI 1차대회 대비 모의고사 (2주차)

쇼핑 2
Subtask
2s 1024MB

Problems

상점에는 N 개의 상품이 있으며 상품에는 1 에서 N 까지의 번호가 매겨져 있다.

각 상품에는 정가와 종류가 정해져 있다.

상품 i\ ( 1≤i≤N )의 정가는 P_i 원 이다.

상품의 종류는 1 이상 M 이하의 정수로 나타내고, 상품 i\ ( 1≤i≤N )의 종류는 A_i 이다.

상점은 세일을 하기로 했다. 세일은 M 일간 계속되고, j 일째( 1≤j≤M )에는 종류 j 의 상품을 모두 정가의 반값으로 살 수 있다.

판매 기간 동안 Q 명의 고객이 상점을 방문했다. 고객은 1 에서 Q 까지 번호가 매겨져 있다.

손님 k\ ( 1 ≤ k ≤ Q )는 판매의 T_k 일째에 상점을 방문하여 상품 L_k , L_k+ 1 ,\ ...,\ R_k 를 하나씩 샀다.

판매의 효과를 조사하기 위해 각 고객이 상품을 사는 데 사용한 금액을 알고 싶다.

상품 정보와 고객 정보가 주어지면 각 고객이 상품을 구입하는 데 사용한 금액을 구하는 프로그램을 작성하시오.


Input

입력은 다음과 같은 형식으로 주어진다.

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

  • 1 \le N,M,Q \le 200\ 000

  • 2 \le P_i \le 10^9 (1 \le i \le N), P_i는 짝수.

  • 1 \le A_i, T_k \le M (1 \le i \le N), (1 \le k \le Q)

  • 1 \le L_k \le R_k \le N (1 \le k \le Q)

  • 모든 입력은 정수다.


Output

Q 행에 걸쳐 k 번째 행 ( 1 ≤ k ≤ Q )에 고객 k 가 상품을 사는 데 사용한 금액을 출력한다.


Subtask

# Score Condition
#115

N, M, Q \le 2\ 000

#220

M=1

#312

M \le 10

#414

A_i \neq A_j (1 \le i < j \le N)

#522

P_i = 2 (1 \le i \le N)

#617

추가 제한 없음


Example #1

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

Example #2

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

Example #3

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

Example #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
11
13
17
8

Example #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
1907757100
3182585150
458514202
1684028078
1064002576
3897234150
2030460064
441379880
2043536529
1009893320
You must sign in to write code.