markdown

D. 树的询问

Roman 种了一棵有 $n$ 个顶点的树。每个顶点上写有一个小写英文字母。顶点 $1$ 是树的根，其余 $n-1$ 个顶点在树中都有一个父节点。每个顶点通过一条边与其父节点相连。顶点 $i$ 的父节点是 $p_i$，并且父节点的编号总是小于该顶点的编号（即 $p_i < i$）。

顶点的深度定义为从根节点沿着边到达该顶点所经过的节点个数。特别地，根节点的深度为 $1$。

我们说顶点 $u$ 在顶点 $v$ 的子树中，如果从 $u$ 出发，不断向父节点移动，可以到达 $v$。特别地，顶点 $v$ 也在它自己的子树中。

Roman 会给你 $m$ 个询问，第 $i$ 个询问包含两个数 $v_i$ 和 $h_i$。考虑所有在顶点 $v_i$ 的子树中且深度为 $h_i$ 的顶点。判断能否用这些顶点上的字母构成一个回文串。顶点上的字母可以按任意顺序重新排列，但必须使用所有字母。

输入

第一行包含两个整数 $n, m$（$1 \le n, m \le 500\,000$）—— 分别表示树中的顶点数和询问数。

接下来一行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$ —— 从第 $2$ 个到第 $n$ 个顶点的父节点编号（$1 \le p_i < i$）。

再下一行包含 $n$ 个小写英文字母，其中第 $i$ 个字母是写在顶点 $i$ 上的字母。

接下来的 $m$ 行描述询问，第 $i$ 行包含两个数 $v_i, h_i$（$1 \le v_i, h_i \le n$）—— 第 $i$ 个询问中的顶点和深度。

输出

输出 $m$ 行。在第 $i$ 行中，如果第 $i$ 个询问中可以用这些顶点上的字母构成回文串，则输出 Yes（不带引号），否则输出 No（不带引号）。

样例

输入

6 5
1 1 1 3 3
zacccd
1 1
3 3
4 1
6 1
1 2

输出

Yes
No
Yes
Yes
Yes

注释

字符串 $s$ 是回文串，如果它从左向右读和从右向左读相同。特别地，空字符串也是回文串。

样例解释：

• 第一个询问中，满足条件的顶点只有顶点 $1$，我们可以构成回文串 "z"。
• 第二个询问中，顶点 $5$ 和 $6$ 满足条件，它们分别包含字母 'c' 和 'd'。无法用它们构成回文串。
• 第三个询问中，在深度 $1$ 且位于顶点 $4$ 的子树中的顶点不存在。我们可以构成空回文串。
• 第四个询问中，在深度 $1$ 且位于顶点 $6$ 的子树中的顶点不存在。我们可以构成空回文串。
• 第五个询问中，顶点 $2$、$3$ 和 $4$ 满足上述条件，它们分别包含字母 'a'、'c' 和 'c'。我们可以构成回文串 "cac"。