Subly went to meet the Chef. As the Chef gets a lot of problems from his friends, he wants Subly to help him find a good programmer.

Subly is given a Binary String and a positive integer k. He has to count the number of sub strings of length k, whose value in Decimal is divisible by 4.

Two sub strings are unique if their starting and ending positions in the original string are different. Two unique sub strings may have same value.

Input:

First line contains a Number N, denoting length of the string,

Second line contains the String.

Third line contains a number Q, denoting the number of queries.

Then, there are Q numbers in each line, call it k, denoting the length of the sub string.

Output:

Print answer to each query in a new line.

Constraints:

1 <= N <= 100000

1 <= Q <= 100000

2 <= k <= N

The string contains '0' and '1' only.