시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 512 MB258444.444%

문제

Boris has a collection of n coins. He put them in a row, so that the i-th coin in a row has value ai.

Boris is planning to take a trip, but he is short of time, so he is planning to take a continuous segment of adjacent coins with him.

Boris would like to answer several queries. For each query he would like to know what is the minimum amount that he would not be able to pay without change, if he take coins from li to ri. Formally, he would like to find minimum positive integer z such that it is impossible to choose a set of coins with numbers from li to ri such that the sum of their values is z.

입력

The first line of input contains two integers n and m (1 ≤ n, m ≤ 150 000) — the number of coins Boris has and the number of queries. The following line contains n integers ai (1 ≤ ai ≤ 109) — the values of coins.

The following m lines describe queries, each line contains two integers li and ri (1 ≤ li ≤ ri ≤ n) — the beginning and the end of the segment of coins Boris takes.

출력

For each query output one integer: the minimal amount that cannot be paid without change by coins from li-th to ri-th.

 

예제 입력 1

5 5
2 1 5 3 1
1 5
1 3
1 1
2 4
2 5

예제 출력 1

13
4
1
2
11