409058: GYM103428 D Period

Zayin have learned how to compute the number of periods of a string recently.

As his girlfriend, Ziyin would like to give Zayin some strings and test whether he really learn the knowledge well. But Ziyin is too lazy to produce strings which are completely different, so she would firstly give Zayin a string, and ask him if she modify the $$$i$$$-th character of the string to #, what is the number of periods of the new string. (Note that Ziyin wouldn't really perform the modification)

It's really a big question for Zayin. Can you help him so that he would not lose face in front of his girlfriend?

The first line contains a string $$$s$$$ ($$$1\le|s|\le 10^6$$$), which only contains lowercase letters.

The second line contains an integer $$$q$$$ ($$$1\le q\le 10^6$$$), indicating the number of queries.

Each of the next $$$q$$$ lines contains an integer $$$i\ (1\le i\le |s|)$$$, indicating Ziyin would modify the $$$i$$$-th character of the string to #.

For each of the $$$q$$$ queries, print an integer indicating the number of periods of the new string after Ziyin's modification.

ccpc
4
1
2
3
4

0
1
1
0

A integer number $$$T$$$ is a period of a string $$$s$$$ if and only if $$$1\le T<|s|$$$ and $$$s[i]=s[i-T]$$$ for every $$$i\in\big(T,|s|\big]$$$.