텍스트 편집기

이네스는 프로그래밍을 막 시작했다. 지금은 빈 문서에 글자를 덧붙이는 기능만 있는 간단한 문서 편집 프로그램을 만들고 있다. 동생 리타는 화면에 뜬 기호를 보고 신이 나서 프로그램을 만지고 싶어 하고, 그래서 이네스는 일을 이어가지 못한다. 이네스는 작업을 계속하려고 이 상황을 리타와 하는 놀이로 바꾸기로 했다.

먼저 리타가 문서에 아무 글이나 적는다. 그러면 이네스가 길이 $W$짜리 구간을 하나 골라, 그 구간 안에 서로 다른 기호 나열이 몇 개나 들어 있는지 맞혀 보라고 한다. 리타는 신나서 놀이에 뛰어들었지만 문제가 하나 있다. 이네스도 자기가 낸 질문의 답을 구하는 프로그램을 아직 쓸 줄 모른다.

리타가 적은 글과 이네스의 질문이 주어진다. 각 질문마다 그 구간에 들어 있는 서로 다른 부분 문자열의 개수를 구하라. 부분 문자열은 문서에서 연속한 글자를 이어 붙인 것이고, 빈 문자열은 세지 않는다.

첫째 줄에 리타가 적은 글 $D$가 주어진다. 글은 알파벳 소문자 $a$부터 $z$까지로만 이루어져 있다. 둘째 줄에 질문의 개수 $Q$와 이네스가 고르는 구간의 고정 길이 $W$가 공백을 사이에 두고 주어진다. 다음 $Q$개의 줄에는 질문을 나타내는 정수 $i$가 한 줄에 하나씩 주어진다. 이 질문은 구간 $[i, i+W-1]$을 뜻한다.

각 질문의 답을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.

• $1 \le |D| \le 100\,000$, $|D|$는 글의 길이
• $1 \le Q \le 100\,000$
• $1 \le W \le |D|$
• $1 \le i \le |D| - W + 1$, 구간의 위치는 1부터 센다