It's the TechCrunch. The Nucleus' compression algorithm has already the Weissman Score of 2.89. Pied Piper team has to win this competition. Dinesh, Gilfoyle and Erlich are quite sure that they are wasted. But Richard has faith that he can get a better Weissman Score. Since he has only one night, he wants your help. He asks you to code a fast algorithm to solve a problem. You will be given an array of N numbers and a range [L, R]. You have to find the product of all the number in the range [L, R] (including the numbers at both L and R indexes) and return the answer modulo some number M. This is your chance to make an impression on The Pied Piper Team.
Input
First line contains N
Second line contains N integers A[i] separated with space
Third line contains the number of queries Q
Next Q line contains three, space-separated integers L, R and M
Output
Print the product of the given range modulo M for every query.
Constraints
1 <= N <= 100000
1 <= A[i] <= 100
1 <= L <= R <= N
1 <= M <= 109
1 <= Q <= 105
