#5268. 加密

内存限制:256 MiB 时间限制:10 Sec

题目描述

身为特工,Star的任务除了获取敌人的情报外,当然还包括传递己方的情报。考虑到利用数字进行运算的加密方式
容易被破译,他想到了一个借助字母的加密法。现在有一个包含N个小写字母的字符串S,其下标从0开始。Star用
下列方式得到它对应的密码:
1、光标初始位于下标0处;
2、当光标位于i时,找到一个最长的子串S[j ... j + len - 1],满足j < i,使得S[i ... i + len - 1] = S[j 
... j + len - 1]。然后在密文中追加len、j两个整数,并将光标往后移动len个位置。若对于最大的len,有多个
合法的j与之对应,Star会选择最小者;
3、若不存在合法的len、j,则在密文中依次追加-1和S[i]对应的ASCII码,并将光标往后移动一位;
4、当光标位于下标N时,加密完成,最终得到的密文会是一行偶数个用空格隔开的整数。
现给定某个字符串S,请你输出对应的密文。

输入格式

一行一个字符串S。
N ≤ 500000

输出格式

一行若干个整数,如题目描述。

样例

样例输入


			
tttqqttt

样例输出


			
-1 116 2 0 -1 113 1 3 3 0

数据范围与提示