Inês 刚开始学习编程。她正在编写一个简单的文本处理应用程序。到目前为止，该应用程序仅支持向空白文档中添加文本。她那好动的小妹妹 Rita 对 Inês 屏幕上各种不同的符号非常着迷，想要玩弄这些符号，导致 Inês 无法继续工作。为了能继续工作，Inês 决定把这变成一个给 Rita 玩的游戏。

Document

Inês 会让 Rita 在应用程序中随意输入内容。然后，Inês 会选择文档中宽度为 $W$ 的片段，并向 Rita 提出挑战，让她猜该文本片段中有多少个不同的符号序列。Rita 玩得很开心，但有一个问题：Inês 还不知道如何编写程序来为她自己的问题找到正确答案。你能帮帮她吗？

任务

给定姐妹俩玩的游戏描述：文档中书写的文本以及 Inês 的问题，请为每个问题找出不同（非空）子串的数量。子串是文档中连续字母的序列。

输入格式

第一行包含 Rita 书写的文本。文本仅由字母 $[a - z]$ 组成。第二行包含两个空格分隔的整数：$Q$ 和 $W$。$Q$ 是问题的数量，$W$ 是 Inês 问题的固定宽度。接下来的 $Q$ 行，每行包含一个整数 $i$，描述一个问题，即询问范围 $[i, i + W - 1]$ 内不同子串的数量。

数据范围

$1 \le |D| \le 100\,000$ 文档中的字母数量。 $1 \le Q \le 100\,000$ 问题数量。 $1 \le W \le |D|$ Inês 问题的宽度。 $1 \le i \le |D| - W + 1$ 问题范围采用 1-索引，且在文档边界内。

输出格式

输出包含每个问题的答案，顺序与输入相同，每行一个答案。

样例

输入格式 1

acat
2 3
1
2

输出格式 1

5
6

说明

第一个问题涉及范围 $[1, 3] \to aca$，它有 5 个不同的子串 $\{a, c, ac, ca, aca\}$。 第二个问题对应 $cat$，它有 6 个不同的子串：$\{a, c, t, ca, at, cat\}$。

输入格式 2

portoisamazing
2 7
6
3

输出格式 2

26
28