Clue Generator¶

Estimated time limit: 2.5 seconds. Memory limit: 1024 MB.

The limit is 2 times the slowest median runtime of the reference program on the target platform, rounded up to a multiple of \(0.5\) seconds. See the evaluation environment.

Story¶

“Old PJ is sneaky! Something fishy must have happened!”

Readers may prove for themselves that UNR 2018 Day 2, Problem 3 is a sequence of length \(N\). Each element is an inteRger with absolute value at most \(10^9\).

Old ZY discovers that a zero-sum interval can produce clues. With enough clues, he can build a Clue Generator. Define an interval's clue intensity as the sum of the lengths of all zero-sum subarrays within it.

Old ZY now selects \(M\) intervals from the sequence and asks for the clue intensity of each. To prevent offline processing, every query is encrypted using the previous answer, which is taken to be zero before the first query.

Formal Problem Statement¶

Given an integer sequence \(a_1,\ldots,a_N\) , answer \(M\) queries. For a decoded inclusive interval \([l,r]\) , the answer is

\[ \sum_{l\le s\le t\le r}\left[\sum_{j=s}^{t}a_j=0\right](t-s+1). \]

Brackets denote an indicator: one when the condition holds, zero otherwise. Thus, the answer sums the lengths of all nonempty zero-sum subarrays contained in the query interval.

Let last be the preceding answer, initially zero. After reading raw integers \(u,v\) , compute

\[ x=((u\mathbin{\mathrm{XOR}}\mathrm{last})\bmod N)+1,\qquad y=((v\mathbin{\mathrm{XOR}}\mathrm{last})\bmod N)+1, \]

then set \(l=\min(x,y)\) and \(r=\max(x,y)\) . XOR is bitwise exclusive OR on nonnegative integers. Use the complete previous answer without truncating it to thirty-two bits. Print the current answer and update last . Queries do not modify the sequence, and answers are not reduced modulo anything.

Input Format¶

The first line contains \(N,M\) . The second contains \(a_1,\ldots,a_N\) . Each of the next \(M\) lines contains two raw, undecoded integers \(u,v\) .

Output Format¶

Print \(M\) lines containing the answers in query order.

Samples¶

Sample 1¶

Input¶

Output¶

8
0

Sample 2¶

Input¶

7 2
0 0 0 0 0 0 0
0 6
0 6

Output¶

84
56

Sample 3¶

Input¶

1 2
0
0 0
1000000000 1000000000

Output¶

1
1

Sample Explanation¶

The first query of sample one is \([1,4]\) . Its zero-sum subarrays are \([1,2]\) , \([3,4]\) and \([1,4]\) , with total length eight. With last=8 , the next query decodes to \([1,1]\) and answers zero. Sample two first queries seven zeros, giving \(7\times8\times9/6=84\) . The next query decodes to \([1,6]\) and gives fifty-six. Sample three always queries its only zero.

Constraints and Guarantees¶

\(1\le N,M\le10^5\) , \(|a_i|\le10^9\) , \(0\le u,v\le10^9\) .

Score	Additional constraints
100%	None