Note: We will *not* put pineapple on our pizzas.

At Waterloo, there is a group of 6 friends (Joey, Jason, William, Leon, Nick, and Brian) who like to come together on Friday evenings to discuss math and eat pizza. This week, Nick has found some non-trivial roots to the Riemann Zeta function and received a million dollars in prize money in a coin denominating in an undisclosed number of nano pennies. With his newly found wealth, he plans to take the whole group on a pizza road trip.

The road they will be traveling down is a straight line with ~N~ pizza places that potentially charge different prices.

The night will last ~M~ seconds. At second ~i~ ~(1 \le i \le M)~, the pizza place ~a_i~ changes their price to ~p_i~ nano pennies.

William is getting hungry fast, but Nick can't buy pizza at any place he wants since the owner might not have spare change, therefore, he can only buy pizza at shops whose price is a multiple of his coin denomination. He asks you ~Q~ questions in the form l r x, asking you "What is the earliest time when Nick can go buy the pizza at the restaurants l..r if he can only pay in coins worth x nano pennies?" Please check the sample output for details.

Note: To simplify calculations, assume that Nick has an infinite number of nano pennies.

Input Specification

The first line will contain the integers ~N, M, Q~.

The next line will contain ~N~ integers, indicating the initial prices ~w_i~ ~(1 \le i \le N)~ of the restaurants.

The next ~M~ lines will contain the integers ~a_i, p_i~ ~(1 \le i \le M)~.

The next ~Q~ lines will contain the query in the form ~l_i, r_i, x_i~.

Output Specification

For each query, print a single integer, the earliest time that Nick would be able to buy the pizza. If Nick can buy the pizza initially, print 0. If he can never buy the pizza, print -1.

Constraints

~1 \le N, M, Q \le 3\,000~

~1 \le w_i, p_i, x_i \le 10^{18}~

~1 \le a_i \le N~

~1 \le l_i \le r_i \le N~

For 50% of the points, ~N, M, Q \le 500~.

Note This problem originally had bounds of ~2 \times 10^5~ instead of ~3\,000~.

Sample Input

4 4 6
4 4 4 4
4 5
3 10
2 15
1 20
1 4 2
1 4 5
2 4 5
3 4 5
4 4 5
1 4 7

Sample Output

0
4
3
2
1
-1