회사 문화 1

영선회사에는 내리 칭찬이라는 문화가 있다. 상사가 직속 부하를 칭찬하면 그 부하는 자기 직속 부하를 다시 칭찬하고, 칭찬은 이런 식으로 아래로 계속 이어진다. 결국 어떤 직원이 칭찬을 받으면 그 직원 아래에 있는 모든 부하가 같은 칭찬을 받는다.

모든 칭찬에는 칭찬의 정도를 나타내는 수치가 있다. 칭찬이 아래로 전달될 때 이 수치도 그대로 전달된다.

직속 상사 관계와 최초의 칭찬 정보가 주어질 때, 직원마다 받은 칭찬 수치의 합을 구하라.

첫째 줄에 직원 수 $n$과 최초의 칭찬 횟수 $m$이 주어진다. 직원은 $1$번부터 $n$번까지 번호가 매겨져 있다. ($2 \le n, m \le 100\,000$)

둘째 줄에 $1$번부터 $n$번까지 각 직원의 직속 상사 번호가 차례로 주어진다. 직속 상사의 번호는 자기 번호보다 작다. $1$번은 사장이라 상사가 없으므로 $-1$이 주어진다.

다음 $m$개 줄에 직속 상사에게 칭찬을 받은 직원 번호 $i$와 칭찬 수치 $w$가 주어진다. ($2 \le i \le n$, $1 \le w \le 1\,000$) 한 직원이 여러 번 칭찬을 받을 수도 있다.

사장은 상사가 없으므로 칭찬을 받지 않는다.

$1$번 직원부터 $n$번 직원까지 각자 받은 칭찬 수치의 합을 공백으로 구분해 한 줄에 출력한다.