Problem Description

Score: $ 1100 $ points

The kingdom of Paken consists of a tree structure with $ N $ vertices. The vertex $ i $ $(2 \leq i \leq N)$ is connected to vertex $ P_i $ with an edge of length $ L_i $.

The kingdom has $ M $ types of shops, such as stationery stores and supermarkets. (We will refer to them as type $ 1 $, type $ 2 $, ..., type $ M $). Each vertex has exactly one shop, and vertex $ i $ has shop $ R_i $.

The "inconvenience" of vertex $ i $ is defined as the sum of the shortest distances from vertex $ i $ to the nearest shop of each type: (shortest distance to the nearest shop of type $ 1 $) + (shortest distance to the nearest shop of type $ 2 $) + ... + (shortest distance to the nearest shop of type $ M $).

Determine the inconvenience for each vertex from vertex $ 1 $ to vertex $ N $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ P_2 $ $ P_3 $ ... $ P_N $ $ L_2 $ $ L_3 $ ... $ L_N $ $ R_1 $ $ R_2 $ $ R_3 $ ... $ R_N $

The first line contains the number of vertices $ N $ and the number of shop types $ M $, separated by spaces.

The second line contains the edge information $ P_2, P_3, ..., P_N $, separated by spaces.

The third line contains the edge length information $ L_2, L_3, ..., L_N $, separated by spaces.

The fourth line contains the shop type information $ R_1, R_2, R_3, ..., R_N $, separated by spaces. $ R_i $ represents the type of shop at vertex $ i $.

Output Format

For each vertex $ i $, output the inconvenience of vertex $ i $ on a single line.

Sample Input and Output

Sample Input #1

5 2
1 2 1 2
3 5 2 4
2 1 2 1 1

Sample Output #1

2
3
5
2
7

Sample Input #2

10 3
1 2 3 3 1 6 7 8 8
2 3 5 3 1 1 6 2 7
1 3 2 2 3 2 3 1 1 3

Sample Output #2

3
5
8
18
11
2
3
13
17
21

Sample Input #3

5 5
1 2 3 4
1 2 3 4
1 2 3 4 5

Sample Output #3

20
17
15
18
30

Notes/Hints

Note

Due to the large input size of about $7.5\$ per case, it is recommended to use scanf/printf instead of cin/cout in C++.

Constraints

• $ N $ is an integer between $ 1 $ and $ 400,000 $ inclusive.
• $ M $ is an integer between $ 1 $ and $ 400,000 $ inclusive.
• $ P_i $ is an integer between $ 1 $ and $ i - 1 $ inclusive.
• $ L_i $ is an integer between $ 1 $ and $ 1,000,000 $ inclusive.
• $ R_i $ is an integer between $ 1 $ and $ M $ inclusive.
• There is at least one shop of each type from type $ 1 $ to type $ M $.

Subtasks

Subtask 1 \[ $ 55 $ points \]

• Satisfies $N \leq 1,500$.
• Satisfies $M \leq 750$.

Subtask 2 \[ $ 110 $ points \]

• Satisfies $N, M \leq 70,000$.
• Satisfies $ N = M $.

Subtask 3 \[ $ 275 $ points \]

• Satisfies $N, M \leq 70,000$.
• There are at most $ 8 $ shops of the same type in the kingdom.

Subtask 4 \[ $ 330 $ points \]

• Satisfies $N, M \leq 70,000$.

Subtask 5 \[ $ 330 $ points \]

• Satisfies $N, M \leq 400,000$.

见题面 Input 部分

见题面 Output 部分