由于原题 1 秒的时限过于卡常，本评测时限改为 2 秒。但是我们的 std 可以保证在 1 秒内通过官方数据。

时间限制： 1.0 秒 2.0 秒

空间限制： 1024 MB

题目背景

“魔数”是指代码中出现但没有解释的数字常量。即使代码是你亲手写下的，很可能在几个月以后你也不记得这些魔数的意义了。而这道题中魔数的含义，就需要你自己探索了……

在本题中，我们定义：

• $U_0 = 314882150829468584$
• $U_1 = 427197303358170108$
• $U_2 = 1022292690726729920$
• $U_3 = 1698479428772363217$
• $U_4 = 2006101093849356424$
• $f(x)=( x \bmod 2009731336725594113 ) \bmod 2019$

题目描述

有一个长度为 $n$ 的序列 $A$。初始时所有元素依次为从 $1$ 到 $n$ 的正整数，即 $A_i = i\ (1 \leq i \leq n)$。

有 $q$ 次查询，每次查询输入两个整数 $l,r\ (1 \leq l \leq r \leq n)$，你需要依次进行以下操作：

• 设 $s = f(A_l) + f(A_{l + 1}) + \cdots + f(A_r)$；
• 输出 $s$；
• 设 $t=s \bmod 5$；
• 令 $A_l, A_{l+1}, \dots, A_r$ 的每个数都乘以 $U_t$。

请你依次输出每一次查询的答案。

输入格式

从标准输入读入数据。

第一行包含两个正整数 $n, q$。

接下来 $q$ 行，每行输入两个正整数 $l, r$。

输出格式

输出到标准输出。

输出 $q$ 行，每一行依次表示每一次查询的答案。

4 4
1 3
3 4
3 3
1 3

6
1105
1735
4744

100 100
45 74
38 50
7 45
42 62
83 100
50 51
8 11
93 98
64 70
15 87
30 87
13 79
14 81
18 79
70 88
25 39
13 57
55 85
80 92
83 90
54 75
1 61
17 42
25 49
39 77
32 45
83 87
30 47
59 84
25 50
1 82
21 45
72 96
3 85
16 64
52 92
28 29
84 88
26 93
10 67
27 76
57 62
43 69
63 66
5 59
9 46
49 53
35 50
3 19
23 62
38 73
17 68
34 83
42 91
13 92
19 62
17 70
18 75
95 99
35 90
81 91
59 63
5 90
22 87
51 88
25 61
56 91
50 78
11 60
11 18
27 45
57 82
16 54
3 94
33 56
9 71
68 88
24 36
7 64
48 85
58 76
20 43
9 90
24 27
71 97
25 95
73 97
55 83
22 43
53 55
68 88
12 44
25 87
14 46
34 56
15 35
7 80
46 87
23 71
88 93

1785
5741
10423
24915
1647
2154
1872
8559
12936
60048
52916
79974
61897
50541
16819
15646
48044
30156
14581
6906
17346
45805
25217
29837
44539
12602
5964
16894
23972
30665
64047
28029
26086
89745
49102
40236
2297
6040
64456
57625
48151
8311
27574
4166
52887
37703
4922
17603
17729
35771
35915
52458
54055
44140
70298
39690
49407
48808
4775
55131
9378
2839
75644
58663
40660
29344
38759
31862
51760
7924
22539
22003
31095
86980
25718
61094
18995
13703
56434
35626
18678
22776
82576
3233
24072
76470
23887
28161
26150
2017
19769
31420
63547
31533
24513
20199
62729
39286
43276
6109

子任务

所有最终测试数据的生成方式为：

• 按照上表指定 $n, q$；
• 对于每次查询，$l, r$ 均在合法范围内独立均匀随机确定。