Lyndon 분해와 최소 회전

길이가 $N$인 문자열 $S$와 길이가 $M$인 정수 수열 $A$가 주어진다. $S$의 인덱스는 $0$부터 $N-1$까지이고, $A$의 인덱스는 $0$부터 $M-1$까지이다.

길이가 $L$인 비어 있지 않은 문자열이 자신을 $1$칸부터 $L-1$칸까지 순환 이동한 모든 문자열보다 사전순으로 작으면 Lyndon 문자열이라고 한다. 다음 값을 구해 보자.

• $S$를 사전순 비증가하는 Lyndon 문자열들로 분해한 결과
• $S$의 사전순 최소 회전 시작 인덱스
• $A$의 사전순 최소 회전 시작 인덱스

위 조건을 만족하는 Lyndon 문자열로의 분해는 유일하다. 최소 회전이 여러 개라면 가장 작은 시작 인덱스를 택한다.

첫 번째 줄에 두 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(0 \le N, M \le 200\,000)$

두 번째 줄에 알파벳 소문자로 이루어진 문자열 $S$가 주어진다.

세 번째 줄에 수열의 원소 $A_0, A_1, \cdots, A_{M-1}$이 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9)$ 빈 문자열과 빈 수열도 한 줄을 차지한다. 입력 마지막에 연속한 빈 줄은 생략해도 된다.

첫 번째 줄에 분해한 Lyndon 문자열의 개수와 각 문자열의 시작 인덱스를 공백으로 구분하여 출력한다. 시작 인덱스는 오름차순으로 출력한다.

두 번째 줄에 문자열의 최소 회전 시작 인덱스를 출력한다. 세 번째 줄에 정수 수열의 최소 회전 시작 인덱스를 출력한다.

문자열이나 수열의 길이가 $0$이면 그 최소 회전 시작 인덱스로 $0$을 출력한다.