[HNOI2016] 序列 加强版

本题是 [P3246](https://www.luogu.com.cn/problem/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$，则数据按照如下代码生成： ```cpp 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$： ```cpp 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$。