Missing Coin Sum Queries

Source: CSES

Version: Phuoc Hung OJ Extended

Problem

Coin $i$ has positive value $x_i$. Query $[a,b]$ allows each coin in that index range to be used at most once. Find the smallest positive sum that cannot be formed by a subset of those coins.

Input

The first line contains $n,q$, the second line the coin values, and the next $q$ lines contain $a,b$.

Output

Print the smallest missing positive subset sum for every query.

Subtasks

Subtask 1 (20%)

• $n\le 30$, number of queries $\le 30$.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, number of queries $\le 3000$.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le2\cdot10^5$
• $1\le x_i\le10^9$
• $1\le a\le b\le n$

Example

Input

5 3
2 9 1 2 7
2 4
4 4
1 5

Output

4
1
6

Explanation

For range [2,4], coins are [9,1,2]. Sums $1,2,3$ are possible, but $4$ is not.