K. Character Walk
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a string $$$s = s_1 s_2 \dots s_n$$$ consisting of lowercase English letters.

For $$$1 \leq i \leq j \leq n$$$, let $$$s_{i,j}$$$ be the substring of $$$s$$$ from position $$$i$$$ to $$$j$$$ inclusive.

Consider the integer points on the number line: $$$0, 1, \dots, n$$$. From a position $$$x$$$, you may move to another position $$$y$$$ if and only if the substring $$$s_{\,\min(x,y)+1,\; \max(x,y)}$$$ is a palindrome.

You are given $$$q$$$ queries. In the $$$i$$$-th query, you start at position $$$a_i$$$. For each query, determine the minimum number of moves required to reach either position $$$0$$$ or position $$$n$$$.

Input

There is only one test case in each test file.

The first line contains the string $$$s$$$ ($$$1 \leq n \leq 10^6$$$, where $$$n$$$ is the length of $$$s$$$).

The second line contains an integer $$$q$$$ ($$$1 \leq q \leq 10^6$$$).

The third line contains $$$q$$$ integers $$$a_1, a_2, \dots, a_q$$$ ($$$0 \leq a_i \leq n$$$), the starting positions.

Output

Print $$$q$$$ integers in a single line, where the $$$i$$$-th integer is the answer to the $$$i$$$-th query.

Examples
Input
abcdce
2
2 3
Output
2 3
Input
daabaddabaaaxy
2
2 9
Output
2 3
Input
aabaaaqwertyuiopsdfghjklzxcvnm
2
4 6
Output
2 2
Note

In the third example, one possible way to move to position $$$0$$$ (for both queries) is as follows.

  • In the first move, we move to position $$$5$$$ from either position $$$4$$$ or $$$6$$$.
  • Then, we move to position $$$0$$$ from position $$$5$$$.