J. Suffix Structure
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

For a string $$$u = u_1 \dots u_n$$$, let $$$\mathrm{pre}(u, i)$$$ be the prefix $$$u_1 \dots u_i$$$. In particular, $$$\mathrm{pre}(u, 0)$$$ is empty string.

For two strings $$$u = u_1 \dots u_n$$$ and $$$v = v_1 \dots v_m$$$, let $$$u+v$$$ be the concatenation $$$u_1 \dots u_n v_1 \dots v_m$$$.

You are given a string $$$t=t_1 \dots t_m$$$ of length $$$m$$$ and a tree $$$T$$$ with $$$(n + 1)$$$ vertices labeled with $$$0, 1, \dots, n$$$ rooted at vertex $$$0$$$. Each edge is associated with a character. Please note that in this problem, the alphabet may contain more than $$$26$$$ characters.

Consider the following function $$$$$$f(i,j) = \max\{d(x) \mid s_x\text{ is a suffix of }s_i+ \mathrm{pre}(t,j)\}$$$$$$ where $$$s_i$$$ be the concatenation of characters on the shortest path from root to vertex $$$i$$$ and $$$d(i)$$$ be the number of edges on the shortest path from the root to vertex $$$i$$$.

Your task is to compute the values of $$$g_1, g_2, \dots, g_m$$$ where $$$g_j=\sum\limits_{i=1}^{n} f(i,j)$$$.

Note that $$$s_0$$$ is the empty string and empty string is a suffix of any string.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \times 10^5$$$).

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$0 \le p_i \lt i$$$) where $$$p_i$$$ indicates the parent of vertex $$$i$$$.

The third line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) where $$$c_i$$$ indicates that the edge from vertex $$$p_i$$$ to vertex $$$i$$$ is associated with the $$$c_i$$$-th character from the alphabet. It is guaranteed that $$$p_i \ne p_j$$$ or $$$c_i \ne c_j$$$ for all $$$i \ne j$$$.

The fourth line contains $$$m$$$ integers $$$t_1, t_2, \dots, t_m$$$ ($$$1 \le t_i \le n$$$) where $$$t_i$$$ is the $$$i$$$-th character of string $$$t$$$.

It is guaranteed that neither the sum of $$$n$$$ nor the sum of $$$m$$$ will exceed $$$2 \times 10^5$$$.

Output

For each test case output one line containing $$$m$$$ integers $$$g_1, g_2, \dots, g_m$$$ separated by a space.

Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!

Example
Input
2
11 3
0 1 2 0 4 5 4 6 0 9 10
1 3 2 2 1 3 4 1 3 2 1
3 2 4
5 16
0 0 0 1 4
1 2 3 2 2
2 1 3 3 2 1 3 2 1 3 2 2 1 1 2 1
Output
17 26 22
8 5 5 5 5 5 5 5 5 5 5 5 5 5 10 5
Note

Let's calculate $$$f(11, 1)$$$ and $$$f(11, 2)$$$ in the first sample test case to help you further understand. We have $$$s_{11} = \{3, 2, 1\}$$$ so $$$s_{11} + \text{pre}(t, 1) = \{3, 2, 1, 3\}$$$. As $$$s_6 = \{2, 1, 3\}$$$ is its longest suffix existing in the tree, $$$f(11, 1) = d(6) = 3$$$. Also $$$s_{11} + \text{pre}(t, 2) = \{3, 2, 1, 3, 2\}$$$ and $$$s_3 = \{1, 3, 2\}$$$ is its longest suffix existing in the tree, so $$$f(11, 2) = d(3) = 3$$$.