Tuấn là một cậu bé ham học hỏi và thích lập trình. Cậu tìm được một bài toán nhưng vẫn không tìm được cách giải thích hợp. Hãy giúp cậu giải quyết bài toán này nhé.

Cho một dãy số gồm ~N~ số nguyên, ~A_1, A_2, \dots, A_N~. Có ~Q~ truy vấn, mỗi truy vấn gồm 2 số nguyên ~L, R~. Nhiệm vụ của cậu là tìm số lượng đoạn con liên tiếp nhiều nhất trong đoạn từ ~L~ đến ~R~ mà tổng các số trong mỗi đoạn con đó bằng ~0~. Các đoạn con này không được giao nhau.

Input

• Dòng thứ nhất gồm ~2~ số nguyên dương ~N, Q~ ~(1 \le N, Q \le 10^6)~.
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(-10^6 \le A_i \le 10^6)~.
• ~Q~ dòng tiếp theo gồm 2 số nguyên ~L, R~ ~(1 \le L \le R \le N)~.

Output

• Gồm ~Q~ dòng, dòng ~i~ gồm một số nguyên là số lượng đoạn con liên tiếp nhiều nhất trong đoạn ~[L_i, R_i]~ có tổng bằng ~0~.

Scoring

• Subtask 1 (Gồm 30% số điểm): ~N, Q \leq 10^3~
• Subtask 2 (Gồm 70% số điểm): ~N, Q \le 10^6~

Sample Input 1

5 4
-2 2 -2 8 -6 
2 5
1 5
1 4
1 2

Sample Output 1

1
2
1
1

Sample Input 2

4 2
0 0 0 0
1 2
1 4

Sample Output 2

2
4

Notes

Trong ví dụ đầu tiên, dãy gồm ~5~ phần tử và ~4~ truy vấn:

• Với truy vấn thứ nhất gồm đoạn ~[2, -2, 8, -6]~, đoạn con có tổng bằng ~0~ là ~[[2, -2], 8, -6]~ hoặc ~[2, [-2, 8, -6]]~
• Với truy vấn thứ hai gồm đoạn ~[-2, 2, -2, 8, -6]~, số lượng được có tổng bằng ~0~ lớn nhất là ~[[-2, 2], [-2, 8, -6]]~
• Với truy vấn thứ ba gồm đoạn ~[-2, 2, -2, 8]~, đoạn con có tổng bằng ~0~ là ~[[-2, 2], -2, 8]~ hoặc ~[-2, [2, -2], 8]~
• Với truy vấn cuối cùng gồm đọan ~[-2, 2]~, có duy nhất chính nó có tổng là ~0~