Zero Sum Subintervals

You are given a sequence of integers \(c_1, c_2, \ldots, c_N\). You need to answer \(Q\) queries. In each query, you are given two integers \(L\) and \(R\). Your task is to determine the maximum number of non-overlapping subintervals within the segment \([L, R]\) such that the sum of the elements in each subinterval is \(0\).

A subinterval \([i, j]\) (with \(L \le i \le j \le R\)) is valid if and only if

[ \sum_{k=i}^{j} c_k = 0. ]

The chosen subintervals must be non-overlapping.

inputFormat

The first line contains two integers \(N\) and \(Q\) separated by a space.

The second line contains \(N\) integers \(c_1, c_2, \ldots, c_N\) separated by spaces.

Each of the following \(Q\) lines contains two integers \(L\) and \(R\) (1-indexed), representing a query.

outputFormat

For each query, output one line containing a single integer representing the maximum number of non-overlapping subintervals within \([L, R]\) whose elements sum to \(0\).

sample

5 3
1 -1 2 -2 3
1 2
1 4
2 5

1
2
0