제로 게임

0과 1로만 이루어진 문자열 $S$가 주어진다. 심심해서 이 문자열을 가지고 놀려고 한다. 한 번의 연산에서 문자열의 임의의 문자 하나를 골라 문자열 안의 다른 위치로 옮길 수 있다. 예를 들어 $S =$ 0010이라면 첫 번째 0을 맨 뒤로 옮겨 $S$를 0100으로 만들 수 있다.

또한 $Q$개의 수 $K_1, K_2, \ldots, K_Q$가 주어진다. 각 $i$에 대해, $S$에서 시작해 연산을 최대 $K_i$번 사용했을 때 만들 수 있는 연속된 0의 최대 개수를 구하라.

첫째 줄에 문자열 $S$가 주어진다. 둘째 줄에 정수 $Q$가 주어진다. 이어서 $Q$개의 줄에 각각 정수 $K_i$가 한 개씩 주어진다.

각 질의에 대한 답을 한 줄에 하나씩 출력한다.

$2 \le N \le 10^6$이며, $N$은 $S$의 길이이다. $S$는 0과 1로만 이루어져 있다. $1 \le Q \le 10^5$, $N \times Q \le 2 \times 10^7$, $1 \le K_i \le 10^6$이다.