在皇室家族中，名字非常重要！作为皇家历史学家，你被指派分析王国中各位皇室女士的名字规律。

共有 $n$ 位皇室女士，为了方便起见，编号从 $1$ 到 $n$。每位女士的名字由一个大写字母连接她母亲的名字组成。唯一的例外是编号为 $1$ 的女士，她是皇室家族的创始人，她的名字仅由一个大写字母组成。

例如，ENERYS 可能是 AENERYS 的母亲（因为 AENERYS 的名字由大写字母 ‘A’ 连接她母亲的名字 ENERYS 组成）。同样，AENERYS 可能是 DAENERYS 和 YAENERYS 的母亲。

给定所有皇室女士的描述。你的任务是针对某些特定的字符串 $s$，确定有多少位皇室女士的名字以 $s$ 为前缀。

例如，考虑下方的样例输入 1，皇室血统从创始人 S 直接传到 AENERYS（经过 YS、RYS、ERYS、NERYS 和 ENERYS），每位女士恰好有一位女儿。然后 AENERYS 有两位女儿——DAENERYS 和 YAENERYS，其中后者有一位女儿 RYAENERYS。

在这样的家族中，RY 是两位女士名字的前缀：RYS 和 RYAENERYS。E 是 ERYS 和 ENERYS 名字的前缀。N 仅是 NERYS 名字的前缀，而 S 仅是创始人 S 名字的前缀。AY 不是任何皇室女士名字的前缀。

输入格式

第一行包含两个整数 $n$ 和 $k$，其中 $n$ ($1 \le n \le 10^6$) 是皇室女士的总数，$k$ ($1 \le k \le 10^6$) 是查询字符串的数量。

接下来 $n$ 行描述各位皇室女士。第 $i$ 行描述编号为 $i$ 的皇室女士，包含一个大写字母 $c_i$ (‘A’–‘Z’) 和一个整数 $p_i$，其中 $c_i$ 是女士 $i$ 名字的第一个字母，$p_i$ ($p_1 = 0$ 且对于 $i > 1$ 有 $1 \le p_i < i$) 是她母亲的编号（如果是第一位女士，则为 $0$）。所有名字都是唯一的。

剩余 $k$ 行，每行包含一个非空的查询字符串，仅由大写字母组成。所有查询字符串的长度之和最多为 $10^6$。

输出格式

输出 $k$ 行，第 $i$ 行包含名字以第 $i$ 个查询字符串为前缀的皇室女士数量。

样例

输入 1

10 5
S 0
Y 1
R 2
E 3
N 4
E 5
A 6
D 7
Y 7
R 9
RY
E
N
S
AY

输出 1

2
2
1
1
0