Bas1c is attending the collab social meeting of the Computer Society and the Gaming Society. One of the weird game that people play there is "The Sum". The rule is as follow:

Given an integer n and an array A consists of n non-negative integers A₁, A₂,…,A_n.

Each number in A will be projected onto the screen in the following order: The first number is A₁, the second number is A₂,…, the n-th number is A_n, the (n+1)-th number is A₁ and so on.

There are Q questions, each given 2 numbers K and B, and the player needs to calculate the sum of K consecutive integers appearing on the screen starting from the B-th integer.

Bas1c really want to win the prize to impress his friends. Help him answer all the questions!

Input

- First line: An integer n (1 <= n <= 10⁶) and an integer Q (1 <= Q <= 10⁶)

- Second line: An array consisting of N non-negative integers A₁, A₂,…, A_n (0<A_i<10⁹ for every 1 ≤ i ≤ n) separated by a space

- Q following lines: Each containing two numbers K and B (1 ≤ B ≤ 10⁶; 1 ≤ K ≤ 10⁶)

Output

Q lines containing the answer of respective question

Example

Input:

5 2

4 2 6 1 7

3 2

3 9

Output:

9

12

Explanation:

First question: K=3, B=2 then the sum is 2+6+1=9

Second question: K=3, B=9 then the sum is 1+7+4=12

Subtasks:

25% with B+K ≤ N and N,Q ≤ 10³

25% with B+K > N, K ≤ 10³ and Q ≤ 10³