Our universe is an n-dimensional rectangular parallelepiped. The set of dimensions of the universe B = {a[i] : 1<=i<=n}.
A set B such that its first b elements are dimensions of a b-dimensional subparallelepiped.
Scientists faced a number of questions like: what space is inside the k-dimensional subparallelepiped, assuming that the space inside the m-dimensional one is zero.
Write a program that will answer the scientists' questions.
Input:
All numbers are non-negative.
The first line contains integers (n, q <= 10^5) the dimension of our universe and the number of questions scientists are interested in, respectively.
The second line contains n integers - dimensions of the universe, each of which does not exceed (10^18 - 14)
This is followed by q lines of two numbers each, uniquely asking a question of the specified type, which is of interest to scientists - m, k. (m, k <= n)
Output:
The program should output q lines, one number at a time. The i-th line should contain the answer to the i question of the specified type.
Example:
INPUT:
3 1
1 2 3
0 3
OUTPUT:
6
Explanation:
Because the space inside the 0-dimensional subparallelepiped (point) is zero (by condition), then the space inside the 3-dimensional one (the space inside the 3-dimensional one is the volume) is calculated using the usual formula: 1*2*3 = 6
Author: Ivan Shershnev