Zero Game

Interview

Time limit1sMemory limit512 MB

Summary

Given a binary string and Q values K, find for each K the longest run of zeros that can be formed with at most K moves of single characters.

Level: Medium4 of 10
Topics: Sliding window, String, Two pointers
Solved: No attempts yet

Problem

You are given one string $S$ consisting of only 0 and 1. You are bored, so you start to play with the string. In each operation, you can move any character of this string to another position in the string. For example, suppose $S =$ 0010. Then you can move the first zero to the tail, and $S$ becomes 0100.

You also have $Q$ numbers $K_1, K_2, \ldots, K_Q$ . For each $i$ , find the maximum number of consecutive zeroes the string can have if you start with $S$ and use at most $K_i$ operations.

Input

The first line contains the string $S$ . The second line contains the integer $Q$ . Each of the following $Q$ lines contains one integer $K_i$ .

Output

For each query, print the answer on its own line.

Constraints

$2 \le N \le 10^6$ , where $N$ is the length of $S$ . $S$ consists of only 0 and 1. $1 \le Q \le 10^5$ , $N \times Q \le 2 \times 10^7$ , $1 \le K_i \le 10^6$ .

Examples1

Example 1
Input
```
0000110000111110
5
1
2
3
4
5
```
Expected output
```
5
8
9
9
9
```