접미사 배열과 공통 접두사

길이가 $N$인 문자열 $S$가 주어진다. 다음과 같이 정의한 길이 $N$의 세 배열 $SA$, $L$, $Z$를 구해 보자. 문자열과 배열의 인덱스는 $0$부터 $N-1$까지이다.

$S[l,r)$는 인덱스가 $l$ 이상 $r$ 미만인 $S$의 부분 문자열을 뜻한다. 두 문자열 $X$, $Y$의 최장 공통 접두사 길이를 $\operatorname{LCP}(X,Y)$라 하자.

• 접미사 배열 $SA$: $S$의 접미사를 사전순으로 정렬했을 때, 각 접미사의 시작 인덱스
• LCP 배열 $L$: $N>0$이면 $L_0=0$이고, $1\le i<N$에 대해 $L_i=\operatorname{LCP}(S[SA_{i-1},N),S[SA_i,N))$이다.
• Z 배열 $Z$: $0\le i<N$에 대해 $Z_i=\operatorname{LCP}(S,S[i,N))$이다. $N>0$이면 $Z_0=N$이다.

첫 번째 줄에 정수 $N$이 주어진다. $(0 \le N \le 200\,000)$

두 번째 줄에 알파벳 소문자로 이루어진 문자열 $S$가 주어진다. 입력 마지막에 오는 빈 문자열의 줄은 생략해도 된다.

첫 번째 줄에 접미사 배열 $SA$를 출력한다.

두 번째 줄에 LCP 배열 $L$을 출력한다.

세 번째 줄에 Z 배열 $Z$를 출력한다.

각 배열의 원소는 인덱스 순서대로 공백으로 구분하여 출력한다. $N=0$이면 빈 줄 세 개를 출력한다.