Yen-Jen 非常喜欢萝莉！！！

现在，他正在和一个可爱的猫耳萝莉一起解决一个问题。但他昨天喝得太多，脑子还没清醒，所以他请求你帮他解决以下问题！

给定一棵以 $1$ 为根的有根树，共有 $N$ 个顶点（顶点编号从 $1$ 到 $N$）。每个节点上都有一个大写英文字母。

定义一种生成长度为 $L$ 的字符串的方法如下：

• 选择一个起始节点 $X$
• 向父节点移动 $L - 1$ 次
• 每到达一个节点，就将该节点对应的英文字母追加到字符串末尾

现在有 $Q$ 次询问，在第 $i$ 次询问中，给定一个起始节点 $X_i$ 和长度 $L_i$。请计算有多少个起始节点 $Y$（包含 $X_i$ 本身），使得从 $Y$ 出发生成的字符串与从 $X_i$ 出发生成的字符串相同。

输入格式

输入的第一行包含两个整数 $N, Q$。

下一行给出一个字符串 $S$，其中第 $i$ 个字符表示第 $i$ 个节点上的英文字母。

接下来一行包含 $N - 1$ 个整数，第 $i$ 个整数表示节点 $i + 1$ 的父节点。

接下来有 $Q$ 行，第 $i$ 行表示第 $i$ 次询问。每行给出 $X_i, L_i$，含义如题目描述所述。

保证测试数据合法。

• $1 \leq N, Q \leq 3 \times 10 ^ 5$
• $1 \leq X_i, L_i \leq N$

输出格式

输出 $Q$ 行，第 $i$ 行表示第 $i$ 次询问的答案。

样例

样例输入 1

6 3
ABABBA
1 1 3 3 4
2 2
2 1
6 4

样例输出 1

3
3
1