给定一个仅由字符 ‘0’ 和 ‘1’ 组成的字符串 $S$。你感到很无聊，于是开始玩这个字符串。在每一次操作中，你可以将字符串中的任意一个字符移动到字符串中的其他任意位置。例如，假设 $S = \text{‘0010’}$，你可以将第一个 ‘0’ 移动到末尾，此时 $S$ 变为 $\text{‘0100’}$。

此外，你有 $Q$ 个数字 $K_1, K_2, \dots, K_Q$。对于每个 $i$，你想知道如果从初始字符串 $S$ 开始，且最多使用 $K_i$ 次操作，字符串中连续 ‘0’ 的最大数量是多少。为了满足你的好奇心，请编写一个程序来计算这些答案。

输入格式

第一行包含一个字符串 $S$。第二行包含一个整数 $Q$。接下来的 $Q$ 行，每行包含一个整数 $K_i$，表示第 $i$ 次查询中允许的最大操作次数。

• $2 \le N \le 10^6$
• $S$ 的长度恰好为 $N$
• $S$ 仅由 ‘0’ 和 ‘1’ 组成
• $1 \le Q \le 10^5$
• $N \times Q \le 2 \times 10^7$
• $1 \le K_i \le 10^6$

输出格式

对于每个查询，输出一行，包含一个数字，即该查询的答案。

样例

样例输入 1

0000110000111110
5
1
2
3
4
5

样例输出 1

5
8
9
9
9