Distinct Set Summation

Given an array \(a_1, a_2, \dots, a_n\) and a positive integer \(b\), you are to answer \(q\) queries of the form \([l, r, L, R]\). For each query, perform the following steps:

• Create a distinct set \(S = \{a_i : l \le i \le r \land L \le a_i \le R\}\).
• Define the function \(r(k)\) as follows: \[ r(k) = \begin{cases} \min\{x : x \in S\} & \text{if } k = 0,\\ \min\{x : x \in S \land r(k-1) 0\), \(r(k)\) is the next greater element in \(S\) than \(r(k-1)\).
• Calculate the following sum: \[ \sum_{k=0}^{|S|-1} r(k)\,b^k \]

Output the result modulo \(333333333333333397\) (a prime number).

inputFormat

The first line contains three integers \(n\), \(q\), and \(b\) --- the number of elements in the array, the number of queries, and the base for exponentiation, respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the array.

Each of the next \(q\) lines contains four integers \(l\), \(r\), \(L\), and \(R\), representing a single query.

outputFormat

For each query, output a single integer --- the value of \(\sum_{k=0}^{|S|-1} r(k)\,b^k\) modulo \(333333333333333397\), on a new line.

sample

5 2 3
1 2 3 2 4
1 5 2 4
2 4 2 3

47
11