Cho dãy số gồm $n$ số nguyên không âm $a_1,a_2,...,a_n$. Với mỗi truy vấn dạng $lr$ bạn hãy tìm chỉ số $i(l\le i\le r-1)$ nhỏ nhất sao cho $|(a_l+...+a_i)-(a_{i+1}+..+a_r)|$ đạt giá trị nhỏ nhất.

Đầu vào

Dòng đầu chứa số nguyên dương $n$ và $q$ $(2\le n,q\le {10}^5)$ là số phần tử của dãy và số lần truy vấn.

Dòng tiếp theo gồm $n$ số nguyên không âm là các phần tử của dãy có giá trị không vượt quá ${10}^9$.

$q$ dòng tiếp theo, mỗi dòng gồm chứa hai số nguyên dương $l,r$ $(1\le l<r\le n)$.

Đầu ra

Một dòng duy nhất chứa $n-1$ số tự nhiên.

Subtask

$30\mathrm{\%}$ số test có $n\ast q\le {10}^6$.

Ví dụ

Đầu vào:

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

Đầu ra:

4
3
3

Giải thích: Truy vấn đầu tiên ta chia thành hai đoạn $a_1,a_2,a_3,a_4$ và $a_5,a_6$, khác biệt nhỏ nhất là $1$; truy vấn thứ hai chia thành hai đoạn $a_2,a_3$ và $a_4,a_5$, khác biệt nhỏ nhất là $4$; truy vấn cuối cùng đoạn được chia thành $a_3$ và $a_4$ có khác biệt là $1$.