Smallest Unpayable Amount

Time limit4sMemory limit512 MB

Summary

For each query interval, find the smallest positive amount that cannot be formed as a subset sum of the coins in that interval.

Level: Hard9 of 10
Topics: Greedy, Sorting, Segment tree, Binary search
Solved: No attempts yet

Problem

Boris has collected $n$ coins. He laid them out in a row, and the $i$ -th coin in the row has value $a_i$ .

Boris is about to leave on a trip, but he is short of time, so he plans to take one continuous segment of adjacent coins from the row.

Boris wants to answer several queries. For each query he wants to know the smallest amount he cannot pay without receiving change, given that he takes the coins from position $l_i$ to position $r_i$ . Formally, find the smallest positive integer $z$ such that no choice of coins from position $l_i$ to position $r_i$ has values summing to $z$ .

Input

The first line contains the number of coins $n$ and the number of queries $m$ ( $1 \le n, m \le 150000$ ). The second line contains $n$ integers $a_i$ , the values of the coins ( $1 \le a_i \le 10^9$ ).

Each of the next $m$ lines contains two integers $l_i$ and $r_i$ ( $1 \le l_i \le r_i \le n$ ), the first and the last position of the segment Boris takes.

Output

For each query print one integer on its own line: the smallest amount that cannot be paid without change using the coins from position $l_i$ to position $r_i$ .

Examples5

Example 1

Input

Expected output

Example 2
Input
```
1 1
1
1 1
```
Expected output
```
2
```
Example 3
Input
```
1 1
1000000000
1 1
```
Expected output
```
1
```

Example 4

Input

10 5
1 1 1 1 1 1 1 1 1 1
1 10
1 1
3 7
5 10
10 10

Expected output

Example 5

Input

10 6
1 2 4 8 16 32 64 128 256 512
1 10
1 5
2 10
4 4
1 1
6 9

Expected output