부분 문자열의 수와 등장 위치

길이가 $N$인 문자열 $S$와 $Q$개의 패턴 $P_1, P_2, \cdots, P_Q$가 주어진다. $S$의 인덱스는 $0$부터 $N-1$까지이다. 다음 값을 구해 보자.

• $S$의 길이 $1,2,\cdots,N$인 각 접두사와 $S$ 전체에서 서로 다른 비어 있지 않은 부분 문자열의 개수
• 각 패턴이 $S$에 등장하는 횟수와 가장 이른 등장 위치

패턴이 서로 겹쳐 등장하는 경우도 모두 센다.

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

두 번째 줄에 알파벳 소문자로 이루어진 문자열 $S$가 주어진다. 빈 문자열도 한 줄을 차지한다.

세 번째 줄부터 $Q$개의 줄에 걸쳐 알파벳 소문자로 이루어진 패턴 $P_1, P_2, \cdots, P_Q$가 한 줄에 하나씩 주어진다. $(1 \le \lvert P_i \rvert \le 20)$

길이가 $1$인 접두사부터 길이가 $N$인 접두사까지, 서로 다른 비어 있지 않은 부분 문자열의 수를 한 줄에 하나씩 출력한다. 이어서 전체 문자열의 서로 다른 비어 있지 않은 부분 문자열의 수도 한 번 더 출력한다. $N=0$이면 부분 문자열의 수로 $0$을 한 번만 출력한다.

그다음 줄부터 $Q$개의 줄에 걸쳐 각 패턴의 등장 횟수와 가장 이른 시작 인덱스를 패턴이 주어진 순서대로 출력한다. 두 값은 공백으로 구분하여 출력한다. 패턴이 등장하지 않으면 0 -1을 출력한다.