Description

Given a sequence of length $n$: $a_1, a_2, \cdots, a_n$, denoted as $a[1 \colon n]$. Similarly, $a[l \colon r]$ ($1 \leq l \leq r \leq n$) refers to the sequence $a_l, a_{l+1}, \cdots, a_{r-1}, a_r$. If $1 \leq l \leq s \leq t \leq r \leq n$, then $a[s \colon t]$ is called a subsequence of $a[l \colon r]$.

Now there are $q$ queries. Each query gives two numbers $l$ and $r$, $1 \leq l \leq r \leq n$. For each query, find the sum of the minimum values of all distinct subsequences of $a[l \colon r]$. For example, given the sequence $5, 2, 4, 1, 3$, and a query with $l = 1$ and $r = 3$, then $a[1 \colon 3]$ has $6$ subsequences: $a[1 \colon 1]$, $a[2 \colon 2]$, $a[3 \colon 3]$, $a[1 \colon 2]$, $a[2 \colon 3]$, $a[1 \colon 3]$. The sum of the minimum values of these $6$ subsequences is $5 + 2 + 4 + 2 + 2 + 2 = 17$.

Input Format

The first line contains three integers $n$, $q$, $type$, representing the sequence length, the number of queries, and the input method.

The second line contains $n$ integers describing the sequence.

If $type = 0$, then the next $q$ lines each contain two numbers $l$ and $r$, representing the query interval $[l, r]$.

If $type = 1$, then the data is generated by the following code:

namespace gen{
	typedef unsigned long long ull;
	ull s,a,b,c,lastans=0;
	ull rand(){
		return s^=(a+b*lastans)%c;
	}
};

The initial values of s, a, b, c are given on the third line, where s, a, b are all in $[0, 10^9]$, and c is in $[1, 10^9]$. lastans is the value of the previous query answer converted to type unsigned long long, and for the first query it is $0$.

For each query, you can generate $l$ and $r$ in the following way:

l=gen::rand()%n+1;
r=gen::rand()%n+1;
if(l>r) std::swap(l,r);

Output Format

Output one integer in a single line, which is the XOR sum of the answers of all queries after converting each answer to type unsigned long long.

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

28

6 5 1
1 1 4 5 1 4
19 19 8 10

6

Hint

• For $30\%$ of the data, $1 \leq q \leq 10^5$, $type = 0$.
• For the other $70\%$ of the data, $1 \leq q \leq 10^7$, $type = 1$.

Constraints: for $100\%$ of the data, $1 \leq n \leq 10^5$, $-10^9 \leq a_i \leq 10^9$.

Translated by ChatGPT 5