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