【模板】Lyndon 分解

题目描述

这是一道模板题。 读入一个由小写英文字母组成的字符串 $s$ ,请把这个字符串分成若干部分 $s=s_1s_2s_3\cdots s_m$,使得每个 $s_i$ 都是 [$\text{Lyndon Word}$](https://en.wikipedia.org/wiki/Lyndon_word),且 $\forall 1\le i<m:s_i\ge s_{i+1}$。输出 $s_1$ 到 $s_m$ 这些串长度的右端点的位置。位置编号为 $1$ 到 $n$。 一个字符串 $s$ 是一个 $\text{Lyndon Word}$,当且仅当 $s$ 是其所有后缀中最小的字符串。 为了减小输出量,你只需要输出所有右端点的异或和。

输入输出格式

输入格式


一行一个长度为 $n$ 的仅包含小写英文字母的字符串 $s$。

输出格式


一行一个整数,表示所有右端点的异或和。

输入输出样例

输入样例 #1

ababa

输出样例 #1

3

输入样例 #2

bbababaabaaabaaaab

输出样例 #2

23

说明

第一组样例的答案为 `2 4 5`。 第二组样例的答案为 `1 2 4 6 9 13 18`。 - 对于 $20\%$ 的数据,保证 $1\le n\le 1000$; - 对于 $100\%$ 的数据,保证 $1\le n\le 5\times 10^6$。