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 pizza places that potentially charge different prices.
The night will last seconds. At second , the pizza place changes their price to 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 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.
The first line will contain the integers .
The next line will contain integers, indicating the initial prices of the restaurants.
The next lines will contain the integers .
The next lines will contain the query in the form .
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
For 50% of the points, .
Note This problem originally had bounds of instead of .
Sample Input 1
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 1
0 4 3 2 1 -1