Text Processor

Inês is new to programming. She is writing a simple document editor, and so far it can only add text to a blank document. Her little sister Rita is fascinated by the symbols on the screen and wants to play with the app, so Inês cannot get any work done. To keep working, Inês turns the situation into a game for Rita.

Rita writes whatever she likes in the document. Inês then picks a stretch of the document of width $W$ and asks Rita how many distinct sequences of symbols that stretch contains. Rita jumps at the game, but there is a problem. Inês cannot write a program that answers her own questions yet.

You are given the text Rita wrote and the questions Inês asks. For each question, count the distinct substrings inside that range. A substring is a run of consecutive letters of the document, and the empty string is not counted.

The first line contains the text $D$ that Rita wrote. The text is made of the lowercase letters $a$ to $z$ only. The second line contains two integers $Q$ and $W$ separated by a space, where $Q$ is the number of questions and $W$ is the fixed width Inês picks. Each of the next $Q$ lines contains one integer $i$ describing a question about the range $[i, i+W-1]$.

Print the answer to each question on its own line, in the order the questions are given.

• $1 \le |D| \le 100\,000$, where $|D|$ is the length of the text
• $1 \le Q \le 100\,000$
• $1 \le W \le |D|$
• $1 \le i \le |D| - W + 1$, and positions are counted from 1