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