Description

Given an array $a_1,a_2,\dots,a_n$ and a positive integer $b$, please answer $q$ queries of the form $[l,r,L,R]$.

The symbol $\land$ denotes logical AND.

In each query, you need to:

1. Create a set with no duplicates $S=\{a_i:l\le i\le r\land L\le a_i\le R\}$.
2. Define the function $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. Compute the value of the following expression:

All answers are taken modulo $333333333333333397$ (a prime number).

Input Format

The first line contains three integers $n,b,q$.

The next line contains $n$ integers $a_1,a_2,\dots,a_N$.

The next $q$ lines each contain four positive integers $l,r,L,R$, representing one query.

Output Format

Output $q$ lines, each being the answer to the corresponding query.

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

Hint

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): all $a_i$ are pairwise distinct.
• Subtask 6 (11 pts): $L=0,R=333333333333333396$.
• Subtask 7 (67 pts): no additional constraints.

For all testdata, $1\le n,q\le2\times10^5$, $1\le L\le R\le n$, $0\le b,a_i,L,R<333333333333333397$.

Translated by ChatGPT 5