낼 수 없는 최소 금액

보리스는 동전 $n$개를 모았다. 동전을 한 줄로 늘어놓았고, 줄에서 $i$번째 동전의 가치는 $a_i$이다.

보리스는 여행을 떠나려 하지만 시간이 부족해서, 줄에서 서로 붙어 있는 동전 구간 하나를 통째로 들고 가려고 한다.

보리스는 질문 여러 개에 답하고 싶다. 각 질문마다 $l_i$번째 동전부터 $r_i$번째 동전까지 들고 갔을 때, 거스름돈을 받지 않고는 낼 수 없는 최소 금액이 궁금하다. 정확히 말하면 $l_i$번째부터 $r_i$번째까지의 동전 중에서 어떻게 골라도 가치의 합이 $z$가 되지 않는, 가장 작은 양의 정수 $z$를 구해야 한다.

첫째 줄에 동전의 개수 $n$과 질문의 개수 $m$이 주어진다 ($1 \le n, m \le 150000$). 둘째 줄에 동전의 가치 $a_i$가 $n$개 주어진다 ($1 \le a_i \le 10^9$).

다음 $m$개의 줄에 질문이 하나씩 주어진다. 각 줄에는 보리스가 들고 가는 동전 구간의 시작과 끝을 뜻하는 정수 $l_i$와 $r_i$가 주어진다 ($1 \le l_i \le r_i \le n$).

각 질문마다 $l_i$번째 동전부터 $r_i$번째 동전까지로는 거스름돈 없이 낼 수 없는 최소 금액을 한 줄에 하나씩 출력한다.