Neo is looking into The Matrix. From The Matrix, he pulls out a series of numbers. In order to defeat the robot overlords he makes a bet:
If Neo can multiply sets of these numbers faster than the robot overlords, they must release everyone held in The Matrix.

Input Specification

The first line of input contains ~n~ ~(1 \le n \le 10^6)~.
The next line contains ~n~ space separated integers ~n_i~ ~(1 \le n_i \le 8)~.
The next line contains ~q~ ~(1 \le q \le 10^6)~ representing the number of sets Neo must multiply.
The next ~q~ lines each contain two space separated integers, ~q_1, q_2~ ~(1 \le q_1 \le q_2 \le n)~ indicating that Neo must multiply all numbers in the range ~[q_1, q_2]~.

Output Specification

Output ~q~ lines each containing the product resulting from multiplying all numbers in each range. The product will always fit in a 64 bit signed integer.
Solutions in Java are encouraged to use fast input reading.

Sample Input

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

Sample Output

12
48
3