Suffix Array

Time limit3sMemory limit256 MB

Summary

Read a lowercase string of length up to 500000 and print its suffix array and LCP array, writing x for the first LCP entry.

Level: Medium7 of 10
Topics: String matching, Sorting
Solved: No attempts yet

Problem

The suffix array of a string $S$ lists the starting positions of every suffix of $S$ in lexicographic order. Positions are counted from 1. For example, if $S$ is banana, there are six suffixes.

Suffix	Starting position
banana	1
anana	2
nana	3
ana	4
na	5
a	6

Sorted lexicographically, they come out in this order.

Suffix	Starting position
a	6
ana	4
anana	2
banana	1
na	5
nana	3

Reading the starting positions down the sorted table gives [6, 4, 2, 1, 5, 3], the suffix array of banana.

The LCP array is built on top of the suffix array. For each suffix in sorted order it stores the length of the LCP (Longest Common Prefix) shared with the suffix immediately before it. The first suffix has nothing before it, so its value is undefined. For banana the LCP array is [x, 1, 3, 0, 0, 2].

Given a string of length at most 500000, write a program that computes its suffix array and its LCP array.

Input

The first line contains a string $S$ made up of lowercase letters only. The length of $S$ is at most 500000.

Output

Print the suffix array on the first line and the LCP array on the second line, separating values with a single space. Print the first value of the LCP array as x.

Examples2

Example 1

Input

abracadabra

Expected output

11 8 1 4 6 9 2 5 7 10 3
x 1 4 1 1 0 3 0 0 0 2

Example 2
Input
```
banana
```
Expected output
```
6 4 2 1 5 3
x 1 3 0 0 2
```