题目背景

龙年到，帆帆也举起了自己的彩龙灯，他自己也要变成大彩龙啦！

题目描述

帆帆一共有 $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$。

因为本题输入量过大，因此采用如下方式生成询问：

我们使用下面的代码生成一个伪随机数列：

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$ 的作用见输出格式，那么所有询问的参数可以用以下程序生成：

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 能表示的整数范围内。

5 5 0 956144375 1
2 4 1 5 2 

21971409

10 10 0 478178732 1
2 2 1 1 2 1 2 1 2 1 

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$。