龙逐千灯幻
题目背景
龙年到，帆帆也举起了自己的彩龙灯，他自己也要变成大彩龙啦！
题目描述
帆帆一共有 $n$ 盏龙灯，第 $i$ 盏的颜色是 $a_i$。
帆帆认为一段区间 $[l,r]$ 的美观度 $f(l,r)$ 为 $a_l\cdots a_r$ 中的不同颜色个数。
帆帆准备带着自己的龙灯去玩，他一共计划去玩 $m$ 天，第 $i$ 天，他会带着自己的 $1\cdots x_i$ 号龙灯，但是他发现如果把很多龙灯装在一起，那么别人只会注意到其中有多少种不同的颜色。
因此帆帆准备把这 $x_i$ 个龙灯按照编号顺序分成恰好 $k_i$ 个区间，满足每盏灯恰好在一个区间内。
那么帆帆这次出行的美观度就为所有区间的美观度的和。
请你帮帮帆帆最大化每一次出行的美观度。
输入输出格式
输入格式
第一行五个整数 $n,m,id,seed,limx$，分别代表序列长度，询问次数，以及 $\texttt{subtask}$ 编号（样例中的 $id=0$），随机数种子，以及一个和询问有关的参数 $limx$。
因为本题输入量过大，因此采用如下方式生成询问：
我们使用下面的代码生成一个伪随机数列：
```cpp
uint64_t PRG_state;
uint64_t get_number()
{
PRG_state ^= PRG_state << 13;
PRG_state ^= PRG_state >> 7;
PRG_state ^= PRG_state << 17;
return PRG_state;
}
int readW(int l,int r)
{
return get_number()%(r-l+1)+l;
}
```
一开始 `PRG_state=seed`，你每次调用 `readW(l,r)` 会返回一个 $[l,r]$ 内的随机数。
第二行 $n$ 个整数，第 $i$ 个整数代表 $a_i$。
设 $x_i,k_i,c_i$ 表示第 $i$ 组询问需要的参数 $x,k,c$，其中 $c$ 的作用见输出格式，那么所有询问的参数可以用以下程序生成：
```cpp
for (int i = 1; i <= m; ++i) {
x[i] = readW(limx, n);
k[i] = readW(1, x[i]);
c[i] = readW(0, 1e7);
}
```
注：**请不要在运行上述代码段获得各组询问的参数之前调用 `readW()` 函数，否则无法获得正确的询问信息。** 本题不需要利用该伪随机数生成器的特殊性质，你只需将 `get_number()` 视为一个每次调用独立且均匀随机地生成一个无符号 $64$ 位整数的生成器即可。本题也不需要优化伪随机数生成器的内部实现。
输出格式
为了减少输出量，我们使用如下方式进行信息压缩：
如果第 $i$ 组询问的答案为 $ans_i$，其生成参数为 $c_i$，那么你需要输出：
$$\bigoplus\limits_{i=1}^m(ans_i\times c_i)$$
其中 $\bigoplus $ 为异或运算，该值显然一定位于 `long long` 能表示的整数范围内。
输入输出样例
输入样例 #1
5 5 0 956144375 1
2 4 1 5 2
输出样例 #1
21971409输入样例 #2
10 10 0 478178732 1
2 2 1 1 2 1 2 1 2 1
输出样例 #2
2834792说明
### 【样例1解释】
询问分别是：
```
3 1 6121576
5 3 3089509
1 1 4506170
3 1 2821007
1 1 7941511
```
答案分别是:
```
3
5
1
3
1
```
对于第一组询问，要分成一个区间，那么就是 $[1,3]$，美观度就是 $f(1,3)=3$ 。
对于第二组询问，最优的方案是分成 $[1,3],[4,4],[5,5]$，美观度是 $f(1,3)+f(4,4)+f(5,5)=5$
后三个询问同理。
### 【样例2解释】
询问分别是：
```
8 4 6858024
3 2 236530
2 2 8140891
5 3 4562139
8 7 4749403
7 4 4319971
5 1 5063575
3 1 7343109
6 2 1566851
3 1 7959241
```
询问答案分别是：
```
7
3
2
5
8
7
2
2
4
2
```
### 【数据范围】
本题采用捆绑测试。
- 子任务一（$10$ 分）：$1 \leq n\leq 500$。
- 子任务二（$15$ 分）：$1\leq n\leq 3000$。
- 子任务三（$15$ 分）：$m=1$。
- 子任务四（$20$ 分）：$1\le a_i\le 30$。
- 子任务五（$20$ 分）：$1\leq n\leq 4\times 10^4$。
- 子任务六（$20$ 分）：无特殊限制。
对于 $100\%$ 的数据，$1 \leq n\leq 10^5$，$1\leq m\leq 10^6$，$0\leq seed\leq 10^9$，$1\leq limx\leq n$，$1\leq a_i\leq n$。