After Graham and his ~N~ friends finish organizing the candies they got, they decide to find a way to split it! There are ~M~ brands of candy, which are organized in a line ~(1 \le M \le 10^6)~. Now, the hard part: splitting the candy evenly ...

Of course, with every friend group, there exists a distinct power relationship. A side that exploits and a side that's exploited. A side that's devoted, a side receiving devotion. A winner and a loser.

However, Graham's friend group is no ordinary friend group! Graham is a very benevolent ghost, and wishes to give candy to his friends! His friends, moved by his enthusiasm, lets him pick a consecutive sequence from the line of brands.

Graham wants as much candy as possible! Due to Graham's guilt for swindling his friends, he decides to pick the longest sequence which contains the same number of brands he dislikes and likes. After carefully sneaking away to the bathroom, he has ~Q~ queries, and asks you the maximum amount of brands of candy he can take from his friends if he starts picking from the ~i~-th index!

Input Specification

The first line of input will contain an integer ~N~, ~M~, and ~Q~, representing the number of friends Graham has, the number of brands that they've collected, and the number of queries respectively.

The next line will contain a string with length ~M~, containing ~0~'s and ~1~'s. This line represents the line of candy brands! A ~0~ means Graham likes the candy, whereas he dislikes those with a ~1~.

Output Specification

Output the maximum number of candy brands that he can take for each query. Note that it is possible he refuses to take any candy out of the goodness of his heart!

Subtasks

Subtask 1 [20%]

~0 \le N \le 10~

~1 \le M \le 10~, where ~N + 1 \le M~

~1 \le Q \le 10~

Subtask 2 [80%]

~0 \le N \le 10^5~

~1 \le M \le 10^5~

~1 \le Q \le 10^5~

Sample Input 1

5 11 5
01010100011
0
1
6
7
10

Sample Output 1

6
10
0
4
0

Sample Explanation 1

For the first query, Graham can collect the first ~6~ candies from ~[0, 5]~.

For the second query, Graham can collect the candies from ~[1, 10]~.

For the last query, Graham cannot collect any candies since there is only ~1~ candy that he can collect.

Sample Input 2

1 1 1
0
0

Sample Output 2

0

Sample Explanation 2

There is only 1 brand of candy available, and so Graham refuses to take the candy.