Company culture 1

Interview

Time limit2sMemory limit512 MB

Summary

Given each employee's manager and a list of praises, propagate every praise value down the whole subtree and print the total each employee receives.

Level: Medium4 of 10
Topics: Tree, DFS, Prefix sum, Graph
Solved: No attempts yet

Problem

Yeongseon Company has a culture of praise that flows downward. When a manager praises a direct subordinate, that subordinate praises their own direct subordinates, and the praise keeps moving down the chain. So when an employee is praised, every employee below that person receives the same praise.

Every praise carries a number that measures how strong it is. The number is passed down unchanged.

Given the direct manager of each employee and the list of initial praises, compute the total praise value each employee receives.

Input

The first line contains the number of employees $n$ and the number of initial praises $m$ . Employees are numbered from $1$ to $n$ . ( $2 \le n, m \le 100\,000$ )

The second line contains the direct manager of employees $1$ through $n$ , in order. A manager's number is smaller than the employee's own number. Employee $1$ is the president and has no manager, so $-1$ is given for employee $1$ .

Each of the next $m$ lines contains an employee number $i$ who was praised by their direct manager and the praise value $w$ . ( $2 \le i \le n$ , $1 \le w \le 1\,000$ ) The same employee may be praised more than once.

The president has no manager, so the president receives no praise.

Output

Print the total praise value of employees $1$ through $n$ on one line, separated by spaces.

Examples5

Example 1
Input
```
5 3
-1 1 2 3 4
2 2
3 4
5 6
```
Expected output
```
0 2 6 6 12
```
Example 2
Input
```
2 2
-1 1
2 5
2 7
```
Expected output
```
0 12
```

Example 3

Input

6 3
-1 1 2 3 4 5
2 1000
6 1000
2 1000

Expected output

0 2000 2000 2000 2000 3000

Example 4

Input

8 4
-1 1 1 1 1 1 1 1
2 1
3 2
8 3
2 4

Expected output

0 5 2 0 0 0 0 3

Example 5

Input

10 6
-1 1 1 2 2 3 3 4 4 5
2 10
4 5
3 7
9 1
5 2
2 3

Expected output

0 13 7 18 15 7 7 18 19 15