题目描述

众所周知，皇室家族的名字非常有讲究。而作为研究皇室的历史学家的你，最近接到了一个艰巨的任务——分析王国历史中所有皇室夫人的名字。

王国历史上有 $n$ 位皇室夫人，方便起见，我们将其从 $1$ 至 $n$ 编号。除了 $1$ 号夫人外，其余夫人的名字均为一个大写字母连接着她母亲的名字。而 $1$ 号夫人作为王国的首任王后，她的名字只有一个大写字母。

例如，由于 $\text{AENERYS}$ 由 $\text{A}$ 与 $\text{ENERYS}$ 组成，因此 $\text{ENERYS}$ 是 $\text{AENERYS}$ 的母亲。相似地，$\text{AENERYS}$ 是 $\text{DAENERYS}$ 与 $\text{YAENERYS}$ 的母亲。

你知道王国历史上所有皇室夫人的姓名与关系，而你需要完成的任务是，对于其他历史学家感兴趣的名字串 $\boldsymbol{s}$，总共有多少位夫人的名字是以 $\boldsymbol{s}$ 起始的。

例如在样例的皇室族谱中，$\text{S}$ 至 $\text{AENERYS}$ 的这一支（包含 $\text{YS}$、$\text{RYS}$、$\text{ERYS}$、$\text{NERYS}$ 与 $\text{ENERYS}$ 这几位夫人）均只有一位女儿。接下来 $\text{AENERYS}$ 有两位女儿，分别是 $\text{DAENERYS}$，以及女儿是 $\text{RYAENERYS}$ 的 $\text{YAENERYS}$。

在这个皇室家族内，有两位夫人的名字以 $\text{RY}$ 起始，她们是 $\text{RYS}$ 与 $\text{RYAENERYS}$。而 $\text{ERYS}$ 与 $\text{ENERYS}$ 均以 $\text{E}$ 起始。名字以 $\text{N}$ 起始的仅有一位夫人 $\text{NERYS}$。同样地，以 $\text{S}$ 起始的仅有首位王后 $\text{S}$。而没有任何一位夫人的名字以 $\text{AY}$ 起始。

输入格式

第一行有两个整数 $n,k$，分别代表王国历史上皇室夫人总数，以及其他历史学家感兴趣的名字串的个数。

接下来 $n$ 行描述所有皇室夫人的姓名与关系。第 $i+1$ 行描述第 $i$ 位夫人的资料 $c_i$ 与 $p_i$，其中字符 $c_i$ 表示她名字的首位字母，$p_i$ 为她母亲的编号。对于编号为 $1$ 的首位王后，$p_1=0$。所有夫人的名字均不重复。

接下来 $k$ 行，每行为一个大写字母构成的非空串，代表一个其他历史学家感兴趣的名字串。

输出格式

输出 $k$ 行，第 $i$ 行为一个整数，代表总共有多少位夫人的名字是以第 $i$ 个感兴趣的名字串起始的。

样例

输入： $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

输出： $2$ $2$ $1$ $1$ $0$

数据范围与提示

$1\leq n\leq 10^6$，$1\leq k\leq 10^6$，$p_1=0$，特别地，对于 $1\lt i\leq n$，保证有 $1\leq p_i\lt i$。感兴趣的名字串总长不超过 $10^6$。