TLE '17 Contest 6 P6 - 6 Friends

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type
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 to 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.


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



There are no comments at the moment.