Patrick has gone crazy in the problemsetting server and keeps muttering things about pure maths and trees, and all the problems he has written are about trees. The AUCPL audience is sick of this! They want some fun problems again, like multidimensional DP or circular geometry. Can you help the rest of the problemsetting team snap Patrick out of this.

To do this, the team has devised a plan to solve one tree problem. In his ramblings, he was written out a tree called the 'master tree', containing many complex structures. To help classify and make sense of this tree, you have created a number of 'child trees'. Your task is to see how many subtrees the master tree contains that are isomorphic to the child tree, for each of the child trees. Hopefully this result will satisfy Patrick, allowing him to move onto making more fun problems.

Clarifications

• 'tree' in this problem refers to arbitrary rooted trees - each node may have any number of children
• A 'subtree' is the rooted tree formed by taking any node in a tree and cutting the link between it and its parent, keeping the component containing the parent, and rooting the remaining tree at the new node.
• Two trees are 'isomorphic' if they possess the same structural organisation, meaning the same number of nodes and edges, and the same connectivity, even if the ordering is different.

For instance, these two trees are isomorphic:

However, these two are not, as they possess a (hopefully clear) structural difference

Input

The first line contains two space separated integers ~n m~ (~1 \leq n,m \leq 10^5~), where ~n~ is the number of child trees, and ~m~ is the number of nodes in the master tree.

The next line contains ~n~ space-separated integers ~C_1\ \dots\ C_n~ (~1 \leq C_i \leq 10^5~) - each ~C_i~ refers to the number of nodes in the ~i~th child tree. Moreover, the sum ~\sum C_i \leq 10^6~.

The next line describes the master tree, with ~n-1~ integers ~p_2\ \dots\ p_m~ (~1 \leq p_i \leq m~) — each ~p_i~ representing the parent node of the ~i~th node in the tree, where nodes are labelled ~1~ through ~n~. Since the root (number ~1~) has no parent, you can notice that the first integer in this line is actually the parent of node ~2~, and so on.

The next ~m~ lines each describe the structure of each child tree, in accordance with the cardinalities found in the second line. The format is the same as the master tree.

Note: If a line describing a child tree is empty, it's because that tree only has one node.

Output

Output ~m~ lines, each containing a single integer. This integer refers to the number of subtrees of the master tree that are isomorphic to the corresponding child tree.

Example

Input 1

2 5
1 3
1 1 2 2

1 1

Output 1

3
1

The master tree has 5 nodes, and there are 2 child trees, with 1 and 3 nodes. They are illustrated:

The first child tree is just a single node. This is isomorphic to the subtree rooted at each of the leaf nodes of the master tree, of which there are 3. The second child tree is a simple triplet as shown, and there is a single isomorphic subtree which is rooted at the left child of the root of the master tree.

Input 2

3 12
1 3 5
1 1 1 2 2 3 3 4 4 10 10

1 1
1 1 3 3

Output 2

7
3
1