Migrated from Lutece 3273 板上加板

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

五千年多前，人类发明了楔形文字。

七十多年前，D.E.Knuth，J.H.Morris 和 V.R.Pratt 发明了 KMP 算法。

而今天，在 UESTC-XCPC 暑假一轮集训中，我们要倡导板上加板：

加一点 KMP

加一点 Z 函数

加一点 Manacher

加一点 后缀排序

加一点 Lyndon 分解

嗯～味道好极了！

$$$$

---

$$$$

对于字符串 $S=S[0,|S|)$，定义其对应的

• $\textsf{fail}$ 数组：对于 $i\in\{0,1,\dots,|S|-1\}$，$\textsf{fail}[i]$ 为 $S[0,i]$ 的最长 border 的长度（$\textsf{fail}$ 的长度为 $|S|$）
• $\textsf{Z}$ 数组（Z 函数）：对于 $i\in\{0,1,\dots,|S|-1\}$，$\textsf{Z}[i]=\textsf{lcp}(S,S_i)$（$\textsf{Z}$ 的长度为 $|S|$）
• $\textsf{P}$ 数组：对于 $i\in\{0,1,\dots,2|S|-2\}$，$\textsf{P}[i] = \max\{\;l+r=i\land S[l,r]=S[l,r]^R\;|\; r-l\;\}$（$\textsf{P}$ 的长度为 $2|S|-1$）
• $\textsf{SA}$ 数组（后缀数组）：$\textsf{SA}$ 是 $0,1,\dots,|S|$ 的一个排列，且对于 $i\in\{1,2,\dots|S|\}$ 有 $S_{\textsf{SA}[i-1]}\prec_\textsf{lex}S_{\textsf{SA}[i]}$（$\textsf{SA}$ 的长度为 $|S|+1$，规定 $S_{|S|}=\epsilon$ 即最小的字符串）
• $\textsf{L}$ 数组：设 $S=\mathbf{w}_1\mathbf{w}_2\dots \mathbf{w}_m$，其中 $\mathbf{w}_1,\mathbf{w}_2,\dots,\mathbf{w}_m$ 均为 Lyndon 串且 $\mathbf{w}_1\succcurlyeq_\textsf{lex}\mathbf{w}_2\succcurlyeq_\textsf{lex}\dots\succcurlyeq_\textsf{lex}\mathbf{w}_m$。（即 $S$ 的 Lyndon 分解，可以证明这种分解存在且唯一）长为 $m+1$ 序列 $x_0=0$，$x_i=x_{i-1}+|\mathbf{w}_i|$。则有 $\forall i={0,1,\dots,|S|},\;\textsf{L}[i]=[i\in\{x_0,x_1,\dots,x_m\}]$（$\textsf{L}$ 的长度为 $|S|+1$）

此外定义一个长为 $|A|$ 的数组 $A$ 的哈希值为

$$\textsf{hash}(A)=\left(\sum_{k=0}^{|A|-1}A[k]\times 233^{|A|-1-k}\right)\bmod 998244353 $$

给出一个字符串 $S$，请求出这个字符串对应的 $\textsf{fail}$、$\textsf{Z}$、$\textsf{P}$、$\textsf{SA}$ 和 $\textsf{L}$ 这五个数组的哈希值。

Input

输入数据只有一行一个字符串 $S$。

Output

输出五行，每行一个整数，分别表示 $S$ 对应的 $\textsf{hash}(\textsf{fail})$、$\textsf{hash}(\textsf{Z})$、$\textsf{hash}(\textsf{P})$、$\textsf{hash}(\textsf{SA})$、$\textsf{hash}(\textsf{L})$。

Samples

aa

1
467
54756
108811
54523

abaaba

12704095
577505732
323543329
385363061
86492954

aaaaaaaa

896215253
402446634
152306105
933340893
15022590

aokjrespdx

0
912100808
574595390
314435979
488466285

abbababbabbababbababbabba

583579254
39106462
494704563
468128253
616648121

Constraints

$1\le |S|\le5\times10^6$

Note

对于第二个样例，有：

$\textsf{fail}=[0,0,1,1,2,3]$

$\textsf{Z}=[6,0,1,3,0,1]$

$\textsf{P}=[1,0,3,0,1,6,1,0,3,0,1]$

$\textsf{SA}=[6,5,2,3,0,4,1]$

$\textsf{L}=[1,0,1,0,0,1,1]$

虽然是模版题，但是并不建议对于字符串了解不深的同学先做此题。

Resources

2024 UESTC ICPC Training for String