题目背景

本题是 P3246 的数据加强版，扩大了询问次数的范围，增加了强制在线，并加入了一组构造数据。

本题的输入输出格式与原题略有不同。

题目描述

给定长度为 $n$ 的序列：$a_1, a_2, \cdots , a_n$，记为 $a[1 \colon n]$。类似地，$a[l \colon r]$（$1 \leq l \leq r \leq N$）是指序列：$a_{l}, a_{l+1}, \cdots ,a_{r-1}, a_r$。若 $1\leq l \leq s \leq t \leq r \leq n$，则称 $a[s \colon t]$是 $a[l \colon r]$ 的子序列。

现在有 $q$ 个询问，每个询问给定两个数 $l$ 和 $r$，$1 \leq l \leq r \leq n$，求 $a[l \colon r]$ 的不同子序列的最小值之和。例如，给定序列 $5, 2, 4, 1, 3$，询问给定的两个数为 $1$ 和 $3$，那么 $a[1 \colon 3]$ 有 $6$ 个子序列 $a[1 \colon 1], a[2 \colon 2], a[3 \colon 3], a[1 \colon 2],a[2 \colon 3], a[1 \colon 3] $，这 $6$ 个子序列的最小值之和为 $5+2+4+2+2+2=17$。

输入格式

第一行三个整数 $n$，$q$，$type$ 表示序列长度，询问数与输入方式。

第二行 $n$ 个整数表示这个序列。

若 $type=0$，接下来 $q$ 行，每行两个数 $l$，$r$，代表询问区间 $[l,r]$。

若 $type=1$，则数据按照如下代码生成：

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

其中，s，a，b，c 的初始值在第三行给出，满足 s，a，b 均在 $[0,10^9]$ 之间，c 在 $[1,10^9]$ 之间。lastans 表示上次询问的答案转化为 unsigned long long 类型后的值，第一次询问时值为 $0$。

每次询问时，你可以通过下面的方式生成 $l$ 和 $r$：

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

输出格式

一行一个整数，表示每次询问的答案转成 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

提示

• 对于 $30\%$ 的数据，$1\le q\le10^5$，$type=0$。
• 对于另外 $70\%$ 的数据，$1\le q\le10^7$，$type=1$。

对于 $100\%$ 的数据，$1\le n\le10^5$，$-10^9\le a_i\le10^9$。