区间 $[l, r]$ 的 popcount 词定义为 $$w(l, r) = s_l s_{l+1} \dots s_{r-1} s_r,$$ 其中 $s_i = \text{popcount}(i) \pmod 2$。这里 $\text{popcount}(i)$ 表示整数 $i$ 二进制表示中 $1$ 的个数。

给定 $n$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$。构建一个超长的字符串 $$S = w(l_1, r_1) + w(l_2, r_2) + \dots + w(l_n, r_n),$$ 其中 “$+$” 表示字符串的拼接。

同时给定 $q$ 次查询。在第 $i$ 次查询中，给定一个位模式 $p_i$，你的任务是报告 $p_i$ 在 $S$ 中作为子串出现的次数。注意，出现的位置可以重叠。

输入格式

输入仅包含一组测试数据。

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 100\,000$)，分别表示区间的数量和查询的数量。

接下来的 $n$ 行中，第 $i$ 行 ($1 \le i \le n$) 包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le 10^9$)，描述第 $i$ 个区间。

接下来的 $q$ 行中，第 $i$ 行 ($1 \le i \le q$) 包含一个由字符 {'0', '1'} 组成的非空字符串 $p_i$，描述第 $i$ 次查询的模式。

保证所有模式串的总长度不超过 $500\,000$。

输出格式

对于每次查询，输出一行，包含一个整数，表示该位模式在 $S$ 中出现的次数。

样例

输入 1

3 5
2 6
1 3
4 8
0
1
11
101
0011010

输出 1

6
7
2
2
1

说明

• $w(l_1, r_1) = w(2, 6) = \text{“10100”}, w(l_2, r_2) = w(1, 3) = \text{“110”}, w(l_3, r_3) = w(4, 8) = \text{“10011”}$。
• $S = w(l_1, r_1) + w(l_2, r_2) + w(l_3, r_3) = \text{“1010011010011”}$。