题目描述

给定长度为 $n$ 的 $01$ 串 $S$ ，$m$ 次询问，每次给出长度为 $w_i$ 的 $01$ 串 $Q$。求 $S$ 中和 $Q$ 长度相同且包含 $1$ 的个数相同的子串的个数

输入格式

第一行两个整数 $n$，$m$ .

第二行字符串 $S$.

接下来 $m$ 行，每行一个 $01$ 串 $Q$

输出格式

输出共 $m$ 行，每行一个整数

样例

输入样例

7 3 
1001101
101
01
0100

输出样例

3
4
0

数据范围与提示

$1 \leq n , m \leq 200000$;

$1 \le \sum_{i = 1}^mw_i \le 2 \times 10^5$