Problem E
Power Queries

You are given a tree on $n$ vertices, rooted at vertex $1$. Each vertex initially has power $0$. You must process $q$ queries on this tree. Each query is of the form “add $p$ power to vertex $v$”. Whenever a nonzero amount of power $p$ is added to a vertex, $p-1$ power is added to each of its children, and this process continues recursively until $p$ reaches zero. This diagram shows the result of one possible query on a tree:

Print the power of each vertex after all queries.

Input

The first line of input contains two integers $n$ and $q$ ($1\le n \le 2\cdot 10^5$, $1\le q \le 2\cdot 10^5$) —the number of vertices and the number of queries, respectively.

The second line of input contains $n-1$ integers $p_2$, $p_3$, $\cdots $ $p_ n$ ($1 \le p_ i < i$) —the parent vertices of vertices $2$ through $n$.

Each of the next $q$ lines contains two integers $v$ and $p$ ($1 \le v \le n$, $1\le p \le 10^9$) —the vertex to add power to, and the amount of power to add, respectively.

Output

Output a single line consisting of $n$ integers —the powers of each vertex, in order, after completing all queries.

12 1
1 1 2 3 3 3 6 6 8 8 11
3 3

0 0 3 0 2 2 2 1 1 0 0 0

14 7
1 1 1 1 3 4 4 5 6 6 6 8 8
9 1
1 10
14 100
8 4
1 2
4 2
6 1

12 10 10 12 10 9 9 13 9 7 7 7 10 110