Lyndon 串：\(s<{\rm suf}'(s)\) 的串 \(s\) 为 Lyndon 串。
引理 1：若 \(u\)、\(v\) 为 Lyndon 串，\(u<v\)，则 \(uv\) 也为 Lyndon 串。
引理 2：若 \(uc\) 为 Lyndon 串的前缀，则 \(uc'(c'>c)\) 为 Lyndon 串。
证明：TODO...
求 \(s\) 的 Lyndon 分解，考虑增量构造。
维护 \(t\) 形如 \(u^xu'\)，\(u\) 为 Lyndon 串，\(u'\) 为 \(u\) 的真前缀。\(t\) 前的 Lyndon 已确定。
维护 \(t\) 的位置 \([i,k]\) 及 \(j=k-|u|\)。分类讨论：
- \(s_j=s_k\)：
- 继续增量过程。
- \(k\gets k+1\)，\(j\gets j+1\)。
- \(s_j<s_k\)：
- 由引理 2，\(u's_j\) 为 Lyndon 串 \(u\) 的前缀，因此 \(u's_k\) 为 Lyndon 串。
- 同时 \(u^y<u's_k(y\ge 1)\)，由引理 1，\(u\gets u^xu's_k\)。
- \(k\gets k+1\)，\(j\gets i\)。
- \(s_j>s_k\)：
- \(u's_j\) 无法与 \(u^y(y\ge 1)\) 组成 Lyndon 串，因此将 \(u^x\) 分为 \(x\) 个 \(u\)，归入 \(s\) 的 Lyndon 分解。
- \(i\gets i+\lfloor \dfrac{j-i}{k-j}\rfloor+1\)。
\(i,j,k\) 单调增，时间复杂度 \(\mathcal{O}(n)\)。
/* luogu_p6114.cpp */
#include <bits/stdc++.h>
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
std::string a; std::cin >> a;
int n = int(a.size());
int ans = 0;
for (int i = 0; i < n; ) {
int j = i, k = i + 1;
for (; k < n && a[j] <= a[k]; ++k) j = a[j] < a[k] ? i : j + 1;
while (i <= j) ans ^= (i += k - j);
}
std::cout << ans << '\n';
return 0;
}