给定一个正整数集合 $A$。对于给定的数字序列 $x$，我们希望知道它在集合 $A$ 中的数字里作为片段（即连续部分）出现了多少次。注意，一个序列 $x$ 可能在给定的 $a \in A$ 中作为片段出现多次，我们需要统计所有这些出现次数。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 5\,000$，$1 \le m \le 500\,000$），分别表示描述集合 $A$ 的行数和查询的数字序列个数。接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$。这些数字满足以下不等式：$1 \le a_1 \le b_1 < a_2 \le b_2 < a_3 \le b_3 < \dots < a_n \le b_n \le 10^{18}$，它们代表集合 $A = [a_1, b_1] \cup [a_2, b_2] \cup [a_3, b_3] \cup \dots \cup [a_n, b_n]$。

接下来的 $m$ 行，每行包含一个数字序列 $x_j$，长度至少为 1，至多为 19 位（数字 0-9）。

输出格式

程序应向标准输出写入 $m$ 行。第 $i$ 行应包含一个整数：$x_j$ 在集合 $A$ 中所有数字里出现的总次数，包括在 $A$ 的各个元素中多次出现的情况。

样例

输入 1

1 3
2220 2223
222
0
07

输出 1

5
1
0