U330219 【模板】BK-Tree

BK-Tree(全称Burkhard Keller Tree)是一种基于[编辑距离（Levenshtein距离）](https://www.luogu.com.cn/problem/P2758)建立的树形结构。常用于根据概念执行拼写检查，也可用于近似字符串匹配。

给出一个词典，每次查询词典中与字符串 $S_i$ 的编辑距离小于等于 $Q_i$ 的字符串个数

第一行包含两个正整数 $N$ 和 $Q$。 接下来的 $N$ 行，每行一个字符串。表示给出的词典。 再接下来 $Q$ 行，每行给出一个整数 $k_i$ 表示模糊程度，一个待查字符串 $S_i$ ，询问与 $S_i$ 的编辑距离小于等于$k_i$的单词有多少个。

共 $Q$ 行 输出词典中与 $S_i$ 编辑距离小于等于 $k_i$ 的单词的个数。

### 样例解释 #### 样例#1解释 - `abcd` 在词典中出现过； - `abc` 与单词 `abcd`、`aabc` 的编辑距离都是 $1$； - `abcdd` 与单词 `abcd`、`abcde`、`abced` 的编辑距离都是 $1$。 #### 样例#2解释 - `noip` 与`lxl`、`fusu`的编辑距离都是 $4$； - `kkksc04` 与单词 `kkksc03` 的编辑距离为 $1$； - `kksc03` 与单词 `kkksc03` 的编辑距离为 $1$； - `fusw` 与单词 `fusu` 的编辑距离为 $1$。 ### 数据范围与约定 - 对于 $0\%$ 的数据，和样例一模一样； - 对于 $50\%$ 的数据，$N,Q \le 50$； - 对于 $100\%$ 的数据，$N \le 3 \times 10^2$ , $Q\le 10^3$ , $1 \le |W_i|,|S_i|\le 20$，所有字符串均由小大写字母与数字构成，保证词典中单词互不相同。