小 Y 是一名大学生，最近正在研究字符串方向的问题。

小 Y 了解到关于字符串的如下定义:

• 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其子串 $s[l: r]$（$1 \leq l \leq r \leq n$）为选择 $s_l, s_{l+1}, \dots, s_r$, 将其顺次拼接得到的新字符串。
• 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其翻转后的结果 $\text{rev}(s)$ 为将 $s_n, s_{n-1}, \dots, s_1$ 顺次拼接，也就是将字符串反序拼接得到的字符串。
• 给定两个长度均为 $n$ 的字符串 $a[1: n], b[1: n]$，我们定义 $a$ 的字典序小于 $b$ 当且仅当存在 $1 \leq i \leq n$，使得对于任意 $1 \leq j < i$，$a_j = b_j$，且 $a_i < b_i$。

---

在了解了上述定义后，小 Y 想到了这样的问题:

定义一个字符串 $t$ 是好的当且仅当 $t<\text{rev}(t)$。其中 $<$ 代表字典序小于。例如，$\text{rev}(\texttt{abcde})=\texttt{edcba}$，因此有 $\texttt{abcde}<\text{rev}(\texttt{abcde})$，所以 $\texttt{abcde}$ 是好的。

给定长为 $n$ 的字符串 $s$ 与序列 $w_1,w_2,\cdots,w_n$，以及奇数 $x$，接下来会进行 $q$ 次询问。

第 $t$ 次询问给定 $1\le l_t\le r_t\le n$，设所有满足下列性质的 $k$ 从小到大为 $k_1 < k_2 < \cdots < k_m$：

• $l_t\le k\le r_t$；
• $s[l_t:k]$ 是好的。

请求出 $\sum\limits_{i=1}^mw_{k_i}x^i\bmod 2^{64}$。特别地，如果没有满足条件的 $i$，则答案为 $0$。

输入格式

为了避免输入量过大，$q$ 组询问的前 $q'$ 组手动输入，后 $q-q'$ 组需通过给定种子 $e$ 生成。具体生成方式见提示一栏。

第一行六个非负整数 $c,n,x,q,q',e$，其中 $c$ 代表子任务编号，样例中 $c=0$；

第二行一个长为 $n$ 的字符串 $s$；

第三行 $n$ 个非负整数，第 $i$ 个代表 $w_i$；

第四行到第 $q'+3$ 行，每行两个正整数，代表手动输入询问的 $l_t,r_t$。

输出格式

为了避免输出量过大，若第 $t$ 次询问的答案是 $a_t$，请处理完所有询问后输出一个非负整数，代表 $\bigoplus\limits_{t=1}^q(a_t+t^3)\bmod 2^{64}$。

0 6 1 10 9 14
banana
1 10 100 1000 10000 100000 
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
4 5

833

最后一次询问 $l_{10}=4,r_{10}=6$。

所有好子串：$\texttt{ban,banan,an,anan}$。

所有询问的答案分别是

1 3: 100
1 4: 100
1 5: 10100
1 6: 10100
2 3: 100
2 4: 100
2 5: 10100
2 6: 10100
4 5: 10000
4 6: 10000

数据范围

对于所有数据，保证：

• $1\le n\le 2\times10^5$；
• $0\le q'\le q\le 2\times10^6$；
• $q'\le 2n$；
• $0\le x,w_i,e\le 10^9$；
• $1\le l_t\le r_t\le n$；
• $x$ 为奇数；
• $s$ 中仅有小写字母。

特殊性质 A：$s$ 在所有长为 $n$ 的小写字母字符串内均等随机生成。

特殊性质 B：$x=1$；

提示

$l_{q'+1},r_{q'+1},l_{q'+2},r_{q'+2},\cdots,l_{q},r_q$ 的生成方式如下：先使用以 $e$ 为种子的 mt19937 生成器生成 $2(q-q')$ 个 $1\sim n$ 的整数 $p_1,p_2,\cdots,p_{2(q-q')}$，对 $q'< t\le q$，令 $l_t=\min\{p_{2(t-q')-1},p_{2(t-q')}\},\ r_t=\max\{p_{2(t-q')-1},p_{2(t-q')}\}$。由于 uniform_int_distribution 在不同编译器实现情况下可能表现不同，因此手动实现区间随机。

可以参考示例代码进行实现：

#include <iostream>
#include <random>
int c, n, x, q, q_, e, w[200005];
std::string s;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin >> c >> n >> x >> q >> q_ >> e >> s;
for (int i = 1; i <= n; ++i) std::cin >> w[i];
std::mt19937 rng(e);
auto rnd = [&](uint32_t L, uint32_t R) -> uint32_t {
uint64_t range = (uint64_t)R - L + 1;
uint64_t bucket = (1ULL << 32) / range;
uint64_t limit = bucket * range;
uint32_t v;
do {
v = rng();
} while ((uint64_t)v >= limit);
return L + (uint32_t)((uint64_t)v / bucket);
};
unsigned long long res = 0;
for (int i = 1; i <= q; ++i) {
int l, r;
if (i <= q_) {
std::cin >> l >> r;
} else {
l = rnd(1, n), r = rnd(1, n);
if (l > r) {
std::swap(l, r);
}
}
unsigned long long I = i;
unsigned long long ans = 0; // solve this
res ^= ans + I * I * I;
}
std::cout << res << '\n';
return 0;
}

</p>

时间限制：$\require{cancel}\cancel{4\texttt{s}} 6\texttt{s}$。

空间限制：$\texttt{2GB}$