Smallest Unpayable Amount

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$.

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.

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$.