H. Harvesting Apples
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As usual, Jaime's delivery business is growing. However, this time, Jaime has focused more on the task of planting and harvesting apples for delivery. During this apple harvesting season, Jaime has placed $$$N$$$ baskets in a row, numbered from $$$1$$$ to $$$N$$$. Each basket has a maximum capacity, $$$c_i$$$, of apples it can hold at any given time.

At the end of each day's harvest, Jaime chooses a basket, $$$b$$$, and adds the $$$a_d$$$ harvested apples to it. The basket cannot store more apples than its maximum capacity. If Jaime exceeds the basket's capacity while adding the apples into it, he takes the excess and saves it for later use as food.

Since Jaime's ultimate goal is to deliver the harvested apples, he has come up with a series of questions to better understand how his harvest business works. For each question, Jaime would like to know how many apples he would have in the baskets from $$$L$$$ to $$$R$$$ after day $$$D$$$, if he had taken those baskets for delivery.

Help Jaime write a program that, given the capacity of the baskets, the selected basket for each day, and the quantity of harvested apples, can answer each of the questions Jaime has to better understand his business.

Input

The first line of input contains three integers separated by a space $$$N$$$ ($$$1 \leq N \leq 10^5$$$), $$$M$$$ ($$$1 \leq M \leq 10^5$$$), and $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), representing the number of baskets, the number of days in the harvesting season, and the number of questions Jaime wants to answer.

The next line contains $$$N$$$ integer numbers separated by a space, where the $$$i$$$-th number represents the capacity $$$c_i$$$ ($$$1 \leq c_i \leq 10^6$$$) of the $$$i$$$-th basket.

The next $$$M$$$ lines contains two integer numbers separated by a space $$$b_i$$$ ($$$1 \leq b_i \leq N$$$), and $$$a_i$$$ ($$$0 \leq a_i \leq 10^6$$$), representing the basket selected on the $$$i$$$-th day and the $$$a_i$$$ apples that were harvested on that day.

Each of the next $$$Q$$$ lines contains three integer numbers separated by a space $$$D$$$ ($$$1 \leq D \leq M$$$), $$$L$$$, and $$$R$$$ ($$$1 \leq L \leq R \leq N$$$), representing the $$$i$$$-th question on Jaime's list.

Output

Print $$$Q$$$ lines, where the $$$i$$$-th line is the answer to the $$$i$$$-th query in the input.

Example
Input
3 5 5
10 1 5
1 10
3 5
1 5
2 4
3 1
1 2 3
5 1 1
1 1 1
5 1 3
3 2 3
Output
0
10
10
16
5