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 $\land$ symbol denotes a logical AND.

For each query, you need to:

1. Create a set $S$ containing unique elements: $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. Calculate the value of the following expression:

$$\sum_{k=0}^{|S|-1}r(k)b^k$$

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

Input

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 a query.

Output

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

Examples

Input 1

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

Output 1

99999999999776691
30000000001494126
99999999999997821
332333333323322794
33333

Input 2

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

Output 2

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

Subtasks

• Subtask 1 (2 pts): $n, q \le 5000$;
• Subtask 2 (3 pts): $n, q \le 5\times 10^4$;
• Subtask 3 (3 pts): $R-L\le 300$;
• Subtask 4 (7 pts): $b=1$;
• Subtask 5 (7 pts): All $a_i$ are distinct;
• Subtask 6 (11 pts): $L=0, R=333333333333333396$;
• Subtask 7 (67 pts): No additional constraints.

For all data, $1\le n, q\le 2\times 10^5$, $1\le l\le r\le n$, $0\le b, a_i, L, R < 333333333333333397$.