【模板】Lyndon 分解

题目描述

这是一道模板题。

读入一个由小写英文字母组成的字符串 $s$ ，请把这个字符串分成若干部分 $s=s_1s_2s_3\cdots s_m$，使得每个 $s_i$ 都是 $\text{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

样例输入 #1

ababa

样例输出 #1

3

样例 #2

样例输入 #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+1$。