题目描述

给定一个数组 $a_1,a_2,\dots,a_n$ 以及正整数 $b$，请回答 $q$ 组 $[l,r,L,R]$ 形式的询问。

$\land$ 符号表示逻辑与。

在这询问里，你需要：

1. 创建无重集合 $S=\{a_i:l\le i\le r\land L\le a_i\le R\}$；

2. 定义函数 $r(k)=\begin{cases}\min (x:x\in S)&k=0\\\min(x:x\in S\land r(k-1)<x)&k\neq0\end{cases}$；

3. 求以下表达式值：

所有答案对 $333333333333333397$（一个质数）取模。

输入格式

第一行三个整数 $n,b,q$。

接下来一行 $n$ 个整数 $a_1,a_2,\dots,a_N$。

接下来 $q$ 行每行四个正整数 $l,r,L,R$，表示一组询问。

输出格式

输出 $q$ 行，代表对应询问答案。

5 33333333333333333 5
333 33 333 33333 3
4 5 0 100000
2 4 0 100000
1 3 0 100000
1 5 0 100000
4 4 0 100000

99999999999776691
30000000001494126
99999999999997821
332333333323322794
33333

33 33333 33
333333333 333333333333 33333333333333 33333333333 33333 333333333333333 33 333 333 333333 3 333333333 3333333 3 333333333 33333333333333 333333333333333 33333333333333 333333 33333333333333 33333333333333 33333333 333333333333333 33333333 33333333 33333 33333333 3333333 33333333 33333333 3333333 33333333 333333333
1 33 3 333333333333333
13 15 333333 333333333333333
15 18 3333333333333 33333333333333
13 30 3 33333333333
3 27 33333 3333333333
25 28 333333 33333333333333
6 30 333 33333333333333
4 32 33333333333333 333333333333333
4 13 33333333 33333333333333
14 28 3333333 33333333333333
17 31 3 33333333333333
21 32 33333 333333333333333
1 2 333333 3333333333333
1 10 3333333 333333333
6 15 33333 333333
5 13 33333 333333333333
4 17 3333333333333 33333333333333
8 28 33333 33333333333333
14 15 3333 333333333333
15 26 333333333 333333333333333
17 25 33333333 333333333333333
13 25 333333 333333333333
8 33 333333 33333333333333
16 17 33333333333 333333333333
24 26 3333333333 333333333333333
23 24 3 333
28 29 333333333 33333333333333
17 25 33 3333
6 7 333333 33333333333
7 12 3333 33333
17 28 3333333333333 3333333333333
11 17 333333 333333
11 17 333333 333333

5381244831822484
11111003322222
33333333333333
187453349930639529
209467718277680736
1111103322222
38102950517542902
111033333333320121
1111100333322222
271584825962251762
259223255302742554
221819973789694611
11111000333322222
333333333
333333
312336974059655685
33333333333333
214323286321378781
333333333
74099999892219735
74099999592219735
12336407395622288
70337133069920353
0
0
0
0
0
0
0
0
0
0

提示

Idea：nzhtl1477，Solution：ccz181078，Code：w33z，Data：w33z

• Subtask 1（2 pts）：$n,q\le5000$；
• Subtask 2（3 pts）：$n,q\le5\times10^4$；
• Subtask 3（3 pts）：$R-L\le 300$；
• Subtask 4（7 pts）：$b=1$；
• Subtask 5（7 pts）：所有 $a_i$ 互不相同；
• Subtask 6（11 pts）：$L=0,R=333333333333333396$；
• Subtask 7（67 pts）：无额外限制。

对于所有数据，$1\le n,q\le2\times10^5$，$1\le L\le R\le n$，$0\le b,a_i,L,R<333333333333333397$。