# 端倪发生器

预估时间限制：2.5 秒。内存限制：1024 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

> “老PJ阴啊，这一定发生了什么端倪！”

读者可以自行证明，2018年的 UNR Day 2 T3 是一个长度为 $N$ 的序列，每个元素都是绝对值不超过 $10^9$ 的整shun。

老ZY发现，一段和为零的区间能够发生端倪。如果有足够多的端倪，就能制造出端倪发生器。我们把一段区间的端倪强度定义为：其中所有和为零的子区间的长度之和。

现在，老ZY要在这个序列中选择 $M$ 个区间，询问每个区间的端倪强度。为了防止你离线处理，询问使用上一次的答案加密；第一次询问前，上一次答案视为零。

## 形式化问题描述

给定长度为 $N$ 的整数序列 $a_1,\ldots,a_N$ .回答 $M$ 次询问。对于解码后的闭区间 $[l,r]$ ，答案为

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

方括号表示条件成立时为一，否则为零。即把询问区间内所有非空、和为零的子区间长度相加。

令 `last` 为上一询问的答案，第一次询问前为零。每次读到原始整数 $u,v$ 后，计算

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

再令 $l=\min(x,y)$ 、$r=\max(x,y)$ .`XOR` 为非负整数的按位异或，使用完整的上一答案，不截断为三十二位。输出本次答案后更新 `last` .询问不修改序列，答案不取模。

## 输入格式

第一行两个整数 $N,M$ .第二行 $N$ 个整数 $a_1,\ldots,a_N$ .接下来 $M$ 行，每行两个**尚未解码**的整数 $u,v$ .

## 输出格式

输出 $M$ 行，每行一个整数，依次表示各询问的答案。

## 样例

### 样例 1

### 输入

```text
4 2
1 -1 2 -2
0 3
0 0
```

### 输出

```text
8
0
```

### 样例 2

### 输入

```text
7 2
0 0 0 0 0 0 0
0 6
0 6
```

### 输出

```text
84
56
```

### 样例 3

### 输入

```text
1 2
0
0 0
1000000000 1000000000
```

### 输出

```text
1
1
```

## 样例解释

第一组第一次询问为 $[1,4]$ ，零和区间是 $[1,2]$ 、$[3,4]$ 、$[1,4]$ ，长度和为八。随后 `last=8` ，第二次解码为 $[1,1]$ ，答案零。第二组先查询七个零，答案为 $7\times8\times9/6=84$ ；下一次解码为 $[1,6]$ ，答案为五十六。第三组始终查询唯一的零。

## 数据范围与保证

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

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |