题目描述

给你一个字符串，每次询问你一个长度为 $w$ 的区间 $[i,i-w+1]$ 中不同的子串个数

输入格式

第一行一个字符串 $D$。

第二行两个正整数 $Q$ 和 $w$，分别表示询问总数和所有询问的区间长度。

接下来 $Q$ 行，每行一个正整数，表示询问区间的起始位置。

输出格式

对于每个询问，输出一个整数，表示该区间的不同子串个数。

acat
2 3
1
2

5
6

portoisamazing
2 7
6
3

26
28

样例解释：

在第一个样例中：

第一个询问询问区间 $[1,3]\to (\texttt{aca})$ 该区间有5个不同的子串 $\texttt{(a,c,ac,ca,aca)}$

第二个询问询问区间 $[2,4]\to (\texttt{cat})$ 该区间有6个不同的子串 $\texttt{(c,a,t,ca,at,cat)}$

数据规模与约定

对于 $100\%$ 的数据，$1\le W\le |D|\le 10^5,1\le Q\le 10^5,1\le i\le |D|-w+1$。