给你一个由小写英文字母组成的字符串 $s = s_1 s_2 \dots s_n$。

对于 $1 \le i \le j \le n$，令 $s_{i,j}$ 表示 $s$ 中从位置 $i$ 到 $j$（闭区间）的子串。

考虑数轴上的整数点：$0, 1, \dots, n$。从位置 $x$，你可以移动到另一个位置 $y$，当且仅当子串 $s_{\min(x,y)+1, \max(x,y)}$ 是回文串。

给你 $q$ 次询问。在第 $i$ 次询问中，你从位置 $a_i$ 开始。对于每次询问，求到达位置 $0$ 或位置 $n$ 所需的最少移动次数。

输入格式

每个测试文件中只有一组测试数据。

第一行包含字符串 $s$（$1 \le n \le 10^6$，其中 $n$ 为 $s$ 的长度）。

第二行包含一个整数 $q$（$1 \le q \le 10^6$）。

第三行包含 $q$ 个整数 $a_1, a_2, \dots, a_q$（$0 \le a_i \le n$），表示起始位置。

输出格式

在一行中输出 $q$ 个整数，其中第 $i$ 个整数表示第 $i$ 次询问的答案。

样例

输入样例 1

abcdce
2
2 3

输出样例 1

2 3

输入样例 2

daabaddabaaaxy
2
2 9

输出样例 2

2 3

输入样例 3

aabaaaqwertyuiopsdfghjklzxcvnm
2
4 6

输出样例 3

2 2

说明

在第三个样例中，一种移动到位置 $0$ 的可能方式（对于两次询问均适用）如下：

• 在第一次移动中，我们从位置 $4$ 或 $6$ 移动到位置 $5$。
• 然后，我们从位置 $5$ 移动到位置 $0$。