题目描述

给定两个字符串 $a,b$，你要求出两个数组：

• $b$ 的 $z$ 函数数组 $z$，即 $b$ 与 $b$ 的每一个后缀的 LCP 长度。
• $b$ 与 $a$ 的每一个后缀的 LCP 长度数组 $p$。

对于一个长度为 $n$ 的数组 $a$，设其权值为 $\operatorname{xor}_{i=1}^n i \times (a_i + 1)$。

输入格式

两行两个字符串 $a,b$。

输出格式

第一行一个整数，表示 $z$ 的权值。

第二行一个整数，表示 $p$ 的权值。

aaaabaa
aaaaa

6
21

提示

样例解释：

$z = \{5\ 4\ 3\ 2\ 1\}$，$p = \{4\ 3\ 2\ 1\ 0\ 2\ 1\}$。

数据范围：

对于第一个测试点，$|a|,|b| \le 2 \times 10^3$。

对于第二个测试点，$|a|,|b| \le 2 \times 10^5$。

对于 $100\%$ 的数据，$1 \le |a|,|b| \le 2 \times 10^7$，所有字符均为小写字母。