Comet OJ

C1910 [Contest #14]序列

内存限制：256 MB 时间限制：1000 ms

题目描述

Ynoi 是个喜欢序列的女孩子，现在她出了一个序列题。

一些定义如下：

一个区间 $[l,r]$ 被称为序列 $a$ (下标从 1 开始) 的一个「极大连续段」当且仅当以下三个条件都满足：

  1. $a_{l...r}$ 的值全部相等

  2. $l = 1$ 或 $a_{l-1} \not= a_l$

  3. $r = n$ 或 $a_{r+1} \not= a_r$

而一个序列的权值为它的「极大连续段」个数。

举例来说，序列 1 1 3 3 2 有三个极大连续段，下标的区间分别为：$[1,2]$、$[3, 4]$、$[5, 5]$，所以此序列权值为 $3$。


最初， Ynoi 手上有一个长度为 $n$ 所有值皆为 $0$ 的序列，此序列编号为 $1$。

Ynoi 将对手上的所有序列进行 $m$ 次操作，第 $i$ 次操作有两个参数 $l_i, r_i$，操作过程如下：

操作前 Ynoi 手上会有 $2^{(i-1)}$ 个序列，Ynoi 会把每个序列复制两份，原先编号为 $k$ 的序列复制得到的两个序列新的编号为 $2k−1$ 与 $2k$，在复制结束后，Ynoi 手上一共有 $2^i$个序列。接着，Ynoi 会把所有编号为奇数的序列中，下标在 $l_i \sim r_i$ 的值都修改为 $i$。

每次操作完后，请你告诉 Ynoi 手上 $2^i$ 个序列的权值和。

输入格式

第一行输入两个正整数 $n, m$，分别描述 Ynoi 的序列长度和 Ynoi 进行的操作次数。

接下来有 $m$ 行，第 $i$ 行有两个正整数 $l_i, r_i$，为 Ynoi 第 $i$ 次的操作的参数。

  • $1 \le n ,m \le 2000$

  • $1 \le l_i \le r_i \le n$

输出

输出 $m$ 行，每行一个整数表示操作后询问的答案，答案可能很大，对 $20050321$(是个质数) 取模后输出即可。

样例

样例输入 1

5 2
1 3
3 5

样例输出 1

3
7

样例输入 2

8 5
1 3
3 5
4 8
5 7
2 4

样例输出 2

3
9
19
52
110

样例输入 3

2 24
2 2
2 2
2 2
1 2
1 2
2 2
2 2
1 1
1 2
1 2
2 2
1 2
2 2
1 1
1 2
2 2
1 2
1 2
2 2
1 2
1 1
1 1
1 2
1 2

样例输出 3

3
7
15
23
39
103
231
487
743
1255
3303
5351
13543
29927
46311
111847
177383
308455
832743
1357031
3454183
7648487
11842791
181078

提示