Prokhor is doing an internship lasting $n$ calendar days at an IT company. Prokhor works in the support department, so he has a complex schedule of working days and days off during his internship.
In addition to his scheduled days off, Prokhor has a certain number of "leave days" — additional days off that he can take on any working days.
Prokhor cannot get quality rest on a single day off, so he considers only those days off that are part of a sequence of two or more consecutive days off to be days of quality rest.
You are given $q$ queries, each representing a different number of leave days that Prokhor can take. Your task is to determine, for each query, the maximum number of days of quality rest Prokhor can get during his internship, given the schedule of working days and days off.
Input
The first line of the input contains two integers $n$ and $q$ ($1 \le n \le 100\,000$, $1 \le q \le n+1$).
The next line contains a string $s$ of length $n$, consisting of the characters '0' and '1', representing the internship schedule. In this string, '0' denotes a working day, and '1' denotes a day off.
The next $q$ lines contain $q$ integers $k_i$ ($0 \le k_i \le n$), the number of leave days in the $i$-th query. It is guaranteed that each value $k_i$ does not exceed the number of working days in the internship schedule.
Output
Output $q$ integers — for each value $k_i$, determine the maximum number of days of quality rest Prokhor can get during the internship by choosing $k_i$ additional days off.
Subtasks
| Subtask | Points | $n$ | $q$ | Additional Constraints | Required Subtasks |
|---|---|---|---|---|---|
| 1 | 6 | – | – | All days are working days | – |
| 2 | 11 | – | – | Days off and working days alternate, first day is a day off | – |
| 3 | 12 | – | $q = 1$ | $k_1 = 0$ | – |
| 4 | 19 | – | $q = 1$ | $k_1 = 1$ | – |
| 5 | 11 | $n \le 15$ | – | – | – |
| 6 | 17 | $n \le 1000$ | – | – | 5 |
| 7 | 13 | – | – | No two days off are consecutive in the schedule | 1, 2 |
| 8 | 11 | – | – | – | 1–7 |
Examples
Input 1
3 4 000 0 1 2 3
Output 1
0 0 2 3
Input 2
4 3 1010 0 1 2
Output 2
0 3 4
Input 3
11 6 11010101001 5 2 0 1 4 3
Output 3
11 7 2 5 10 9
Note
In the first example, all three days of the internship are working days. If fewer than two leave days are taken, it is impossible to get any days of quality rest. For $k_3 = 2$ or $k_4 = 3$, one can choose the first $k_j$ days of the internship as leave days, and all of them will be days of quality rest.
In the second example, it is advantageous to take one leave day on the second day of the internship, then the first three days of the internship will be days of quality rest.
Figure 1. Prokhor dreaming of a vacation while working.