시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB52151536.585%

문제

Прохор проходит стажировку продолжительностью $n$ календарных дней в ИТ-компании. Прохор стажируется в службе поддержки, поэтому у него сложный график рабочих и выходных дней на время стажировки.

Кроме выходных, у Прохора есть некоторое количество отгулов --- дополнительных выходных дней, которые он может взять в любые рабочие дни.

За один выходной день Прохор качественно отдохнуть не сможет, поэтому он считает днями качественного отдыха только те выходные дни, которые входят в последовательность из идущих подряд двух или более выходных дней.

Вам даны $q$ запросов --- различных значений количества отгулов, которые может взять Прохор. Ваша задача --- по заданному графику рабочих и выходных дней стажировки определить для каждого запроса, какое максимальное количество дней качественного отдыха за время стажировки может получить Прохор.

입력

Первая строка входных данных содержит два целых числа $n$ и $q$ ($1 \le n \le 100\,000$, $1 \le q \le n+1$).

Следующая строка содержит строку $s$ длины $n$, состоящую из символов <<0>> и <<1>> --- график стажировки. В этой строке символом <<0>> обозначается рабочий день, а символом <<1>> --- выходной.

В следующих $q$ строках находятся $q$ целых чисел $k_i$ ($0 \leq k_i \leq n$) --- количество отгулов в $i$-м запросе. Гарантируется, что каждое значение $k_i$ не превосходит количества рабочих дней в графике стажировки.

출력

Выведите $q$ целых чисел --- для каждого значения $k_i$ определите наибольшее количество качественных дней отдыха, которое может получить Прохор за время стажировки, выбрав $k_i$ дополнительных выходных дней.

서브태스크

번호배점제한
16

Все дни графика --- рабочие

211

Выходные и рабочие дни чередуются, первый день стажировки --- выходной

312

$q = 1$, $k_1 = 0$

419

$q = 1$, $k_1 = 1$

511

$n \le 15$

617

$n \le 1000$

713

В графике нет двух выходных подряд

811

예제 입력 1

3 4
000
0
1
2
3

예제 출력 1

0
0
2
3

예제 입력 2

4 3
1010
0
1
2

예제 출력 2

0
3
4

예제 입력 3

11 6
11010101001
5
2
0
1
4
3

예제 출력 3

11
7
2
5
10
9

노트

В первом примере все три дня стажировки являются рабочими. Если взять менее двух отгулов, дней качественного отдыха получить невозможно. Для $k_3=2$ или $k_4=3$ можно выбрать отгулами первые $k_j$ дней стажировки, и все они будут днями качественного отдыха.

Во втором примере один отгул выгодно взять во второй день стажировки, тогда первые три дня стажировки будут днями качественного отдыха.

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.