Качественный отдых

Прохор проходит стажировку продолжительностью $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$ дополнительных выходных дней.

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

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