Chia đoạn cân bằng

Cho dãy \(A\) gồm \(N\) số nguyên dương. Với mỗi truy vấn \((u, v)\), xét đoạn \(A_u, A_{u+1}, \dots, A_v\). Ta cắt đoạn này tại một vị trí nào đó thành hai phần: phần đầu (tiền tố) và phần sau (hậu tố); một trong hai phần được phép rỗng. Hãy tìm giá trị nhỏ nhất của \(|S_1 - S_2|\), với \(S_1\), \(S_2\) lần lượt là tổng của hai phần.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, \dots, A_N\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một truy vấn.

Output

In ra \(Q\) dòng, dòng thứ \(i\) là đáp án của truy vấn thứ \(i\).

Constraints

• \(1 \le N, Q \le 10^5\).
• \(1 \le A_i \le 10^9\).
• \(1 \le u \le v \le N\).

Sample Input

6 2
2 7 1 8 2 8
1 4
3 6

Sample Output

0
1

Explanation

Truy vấn \((1,4)\): đoạn \(2,7,1,8\) chia thành \((2,7)\) và \((1,8)\), cùng tổng \(9\), chênh lệch \(0\). Truy vấn \((3,6)\): đoạn \(1,8,2,8\) chia thành \((1,8)\) và \((2,8)\) có tổng \(9\) và \(10\), chênh lệch \(1\).