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 \(l\:r\) 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 \leq n, q \leq 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\%\) số test có \(n*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\).