Given a binary String s (max length 10^6)containing 0 and 1 ,and queries array (max length 10^6) containg integers. Return an array ,each index having sum of all 1's in all window sizes of query[i] .

Question

Example

Input

"101101"

Query= [2,3]

Output

for window size 2 :- 10,01,11,10,01 --> 1+1+2+1+1

Sum= 6

for window size 3 :- 101,011,110,101 --> 2+2+2+2

Sum =8

Result =[6,8]

Answer 1

Sure will put the solution.