小 P 和小 B 喜欢玩游戏，他们找到了 skip。skip 告诉了他们这样一个游戏：
- 有一个包含小写字母的字符串 $S$，游戏开始时其为 skip 给定的一个字符串 $S_0$。游戏对小 P 和小 B 计算分数，初始他们的分数都为 $0$。
- 小 P 和小 B 轮流在这个串上操作，小 P 先手。每次操作方可以进行以下操作：
- 选择 $S$ 的一个非空前缀（可以是 $S$ 本身），获得等同于这个前缀在 $S$ 中的出现次数的分数，并将这个前缀从 $S$ 中删掉。
- 如果进行了某次操作后 $S$ 变为空，游戏就结束了。
为了让你更好的理解游戏规则，考虑如下例子：
- 初始时，$S_0 = ababa$；
- 小 P 选择 $ababa$ 的前缀 $a$，获得 3 分，$S$ 变为 $baba$；
- 小 B 选择 $baba$ 的前缀 $ba$，获得 2 分，$S$ 变为 $ba$；
- 小 P 选择 $ba$，获得 1 分，字符串变为空，游戏结束。最终小 P 获得 4 分，小 B 获得 2 分。
小 P 希望最大化小 P 的得分减去小 B 的得分，而小 B 希望最小化这个值。他们想知道在双方都绝顶聪明的情况下，最终小 P 的得分减去小 B 的得分会是多少。
输入格式
标准输入读入数据。
输入仅一行一个小写字母构成的字符串 $S_0$。
输出格式
输出到标准输出。
一个整数，表示双方绝顶聪明的前提下，游戏结束时小 P 的得分减去小 B 的得分的值。
样例 #1
样例输入 #1
ababa
样例输出 #1
2
提示
样例 1 解释
小 P 和小 B 的最优策略为题目描述中给出的策略。
子任务
设 $n$ 为字符串 $S$ 的长度。对于所有测试数据，$1\le n\le 10^6$，且字符串 $S$ 为小写字母构成的字符串。
| 子任务编号 | $n \le$ | 特殊性质 | 分值 |
|---|---|---|---|
| 1 | $5\times 10^3$ | 无 | 10 |
| 2 | $10^6$ | $S$ 的每个字符在 $\{a,b\}$ 中独立均匀随机 | 10 |
| 3 | $10^6$ | $S$ 的每个字符均为 $a$ | 5 |
| 4 | $2 \times 10^5$ | $S$ 的每个字符均为 $a$ 或 $b$ | 25 |
| 5 | $5 \times 10^5$ | 无 | 25 |
| 6 | $10^6$ | 无 | 25 |
时间限制：2s $\texttt{3.5s}$
空间限制：512MB $\texttt{1G}$
鄂公网安备 42010202000505 号