No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Tree Requests

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputRoman planted a tree consisting of *n* vertices. Each vertex contains a lowercase English letter. Vertex 1 is the root of the tree, each of the *n* - 1 remaining vertices has a parent in the tree. Vertex is connected with its parent by an edge. The parent of vertex *i* is vertex *p*_{i}, the parent index is always less than the index of the vertex (i.e., *p*_{i} < *i*).

The depth of the vertex is the number of nodes on the path from the root to *v* along the edges. In particular, the depth of the root is equal to 1.

We say that vertex *u* is in the subtree of vertex *v*, if we can get from *u* to *v*, moving from the vertex to the parent. In particular, vertex *v* is in its subtree.

Roma gives you *m* queries, the *i*-th of which consists of two numbers *v*_{i}, *h*_{i}. Let's consider the vertices in the subtree *v*_{i} located at depth *h*_{i}. Determine whether you can use the letters written at these vertices to make a string that is a palindrome. The letters that are written in the vertexes, can be rearranged in any order to make a palindrome, but all letters should be used.

Input

The first line contains two integers *n*, *m* (1 ≤ *n*, *m* ≤ 500 000) — the number of nodes in the tree and queries, respectively.

The following line contains *n* - 1 integers *p*_{2}, *p*_{3}, ..., *p*_{n} — the parents of vertices from the second to the *n*-th (1 ≤ *p*_{i} < *i*).

The next line contains *n* lowercase English letters, the *i*-th of these letters is written on vertex *i*.

Next *m* lines describe the queries, the *i*-th line contains two numbers *v*_{i}, *h*_{i} (1 ≤ *v*_{i}, *h*_{i} ≤ *n*) — the vertex and the depth that appear in the *i*-th query.

Output

Print *m* lines. In the *i*-th line print "Yes" (without the quotes), if in the *i*-th query you can make a palindrome from the letters written on the vertices, otherwise print "No" (without the quotes).

Examples

Input

6 5

1 1 1 3 3

zacccd

1 1

3 3

4 1

6 1

1 2

Output

Yes

No

Yes

Yes

Yes

Note

String *s* is a palindrome if reads the same from left to right and from right to left. In particular, an empty string is a palindrome.

Clarification for the sample test.

In the first query there exists only a vertex 1 satisfying all the conditions, we can form a palindrome "z".

In the second query vertices 5 and 6 satisfy condititions, they contain letters "с" and "d" respectively. It is impossible to form a palindrome of them.

In the third query there exist no vertices at depth 1 and in subtree of 4. We may form an empty palindrome.

In the fourth query there exist no vertices in subtree of 6 at depth 1. We may form an empty palindrome.

In the fifth query there vertices 2, 3 and 4 satisfying all conditions above, they contain letters "a", "c" and "c". We may form a palindrome "cac".

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/20/2022 14:48:01 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|