Prefix sau khi xếp hạng

Bối cảnh

Mỗi record {price,id} được xếp price tăng, tie id tăng. Sau đó có nhiều query tổng price theo khoảng rank.

Mục tiêu chính là prefix phải build sau khi sort.

Yêu cầu

1. Sort {price,id} theo price asc, id asc.
2. Build prefix price sau sort.
3. Query rank L..R 1-based.

Input

Dòng 1 n; n dòng price id; dòng q; q dòng L R.

Output

q dòng tổng price.

Ràng buộc

1≤n,q≤5000, rank hợp lệ.

Ví dụ 1

Input

5
100 3
50 2
100 1
20 5
70 4
4
1 1
1 3
2 4
1 5

Output

20
140
220
340

Giải thích

Các record được sort theo price tăng, tie id tăng: price lần lượt 20,50,70,100(id1),100(id3). Prefix phải được build trên thứ tự này. Vì thế query rank 1..1 có tổng 20; 1..3 có tổng 140; 2..4 là 50+70+100=220; toàn bộ 1..5 là 340. Các output phản ánh đúng state ranking sau sort.

Ví dụ 2

Input

1
7 9
2
1 1
1 1

Output

7
7

Giải thích

Chỉ có record (price=7,id=9), nên sort không thay đổi thứ tự và prefix sau ranking là 0,7. Cả hai query đều hỏi rank 1..1; công thức pre[1]-pre[0] cho 7 trong mỗi lần. Ví dụ kiểm tra convention rank 1-based và việc prefix được build sau state ranking, dù với n=1 hai state trùng nhau.

Thông tin học tập

• Module: M05
• Buổi: B18
• Loại bài: LAB
• Độ khó: Medium
• Concepts: pair, comparator, sort, prefix after transform, state consistency
• Giới hạn kiến thức: B01-B18
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100