#98. Điểm xếp hạng (Mã bài: RATING)

Cho một dãy số nguyên không âm gồm phần tử, đại diện cho độ khó của kỳ thi. Dãy được sắp xếp không giảm, tức là với mọi .

Với một rating ban đầu là , khi tham gia một kỳ thi có độ khó , rating mới sẽ được cập nhật thành .

Bạn cần trả lời truy vấn. Mỗi truy vấn gồm một rating ban đầu , và một đoạn . Bạn hãy tính rating cuối cùng sau khi tham gia lần lượt các kỳ thi từ đến .

Dữ liệu:

• Dòng đầu tiên chứa số nguyên là số thứ tự của subtask chứa test này.
• Dòng thứ hai chứa hai số nguyên và là số kỳ thi và số truy vấn.
• Dòng thứ ba chứa số nguyên là độ khó của các kỳ thi.
• Trong dòng cuối cùng, dòng thứ chứa ba số nguyên và tương ứng với rating ban đầu và đoạn kỳ thi cần xét trong truy vấn thứ .

Kết quả: Gồm dòng, dòng thứ là rating cuối cùng sau khi tham gia hết các kỳ thi trong truy vấn thứ .

Ví dụ:

Dữ liệu:

1
5 4
1 7 10 20 100
10 1 3
10 3 4
137 1 5
2696 1 5

Kết quả:

8
20
1
2558

Giải thích: Trong truy vấn đầu tiên, rating ban đầu là và tham gia các kỳ thi có độ khó là . Rating thay đổi như sau: .

Giới hạn:

• Subtask ;
• Subtask và ;
• Subtask ;
• Subtask Không có ràng buộc gì thêm.