Problem Description

Given two strings $a, b$, you need to find two arrays:

• The $z$ function array $z$ of $b$, that is, the LCP length between $b$ and each suffix of $b$.
• The LCP length array $p$ between $b$ and each suffix of $a$.

For an array $a$ of length $n$, define its weight as $\operatorname{xor}_{i=1}^n i \times (a_i + 1)$.

Input Format

Two lines, containing two strings $a, b$.

Output Format

The first line contains one integer, the weight of $z$.

The second line contains one integer, the weight of $p$.

aaaabaa
aaaaa

6
21

Hint

Sample explanation:

$z = \{5\ 4\ 3\ 2\ 1\}$, $p = \{4\ 3\ 2\ 1\ 0\ 2\ 1\}$.

Constraints:

For the first test point, $|a|, |b| \le 2 \times 10^3$.

For the second test point, $|a|, |b| \le 2 \times 10^5$.

For $100\%$ of the data, $1 \le |a|, |b| \le 2 \times 10^7$, and all characters are lowercase letters.

Translated by ChatGPT 5