Fax McClad orders a lone fighter to take down multiple enemy ships.

Fax McClad, Croneria's bravest bounty hunter, is commanding a fleet of fighters to engage the Dankey Kang Gang!

The Dankey Kang Gang's ships are clustered into ~N~ groups. The groups form a line and are numbered from ~1~ to ~N~, from left to right. The ~i^\text{th}~ group contains ~a_i~ ships.

Fax can deploy ~K~ different types of fighters, numbered from ~1~ to ~K~. The ~j^\text{th}~ fighter type is designed to engage continuous intervals of groups of enemy ships, but can only destroy at most ~b_j~ enemy ships in total.

Fax wants to plan well ahead for the battle, so he will perform ~Q~ simulations. For each simulation, he will choose fighters of type ~j~ and an interval of groups ~[l,r]~. He will deploy fighters of his chosen type so that each enemy group in his target interval will only be destroyed by one fighter.

Fax wants to know if it is possible, and to save money, the minimum number of fighters he will need to call for each simulation. Can you help him?

Constraints

~1 \le N \le 2 \times 10^5~

~1 \le K \le 50~

~1 \le Q \le 10^5~

~1 \le a_i,b_i \le 10^9~

Subtask	Percentage	Additional Constraints
~1~	~15~	~N,Q \le 1\,000~
~2~	~25~	~K = 1~
~3~	~20~	~N \le 60\,000~
~4~	~40~	No additional constraints.

Input Specification

The first line of input will contain ~N~, ~K~, and ~Q~.

~N~ lines of input follow. The ~i^\text{th}~ line will contain ~a_i~.

~K~ lines of input follow. The ~j^\text{th}~ line will contain ~b_i~.

~Q~ lines of input follow. Each line will be in the form j l r.

Output Specification

For each simulation, output the minimum number of fighters required. If it is not possible, print -1.

Sample Input

6 2 3
1
3
2
5
1
2
4
6
1 1 3
1 3 6
2 1 6

Sample Output

2
-1
3

Explanation for Sample Output

The enemy groups contain ~1,3,2,5,1,2~ ships.

The types of fighters can handle ~4,6~ enemy ships.

For the first query, ~2~ fighters can be deployed: one to destroy groups ~1,2~, and the other to destroy group ~3~.

For the second query, group ~4~ cannot be destroyed by a single fighter.

For the third query, ~3~ fighters can be deployed: one to destroy groups ~1,2,3~, another to destroy group ~4,5~, and one more to destroy group ~6~.