25911번 - 달나라에 사는 토끼와 우주에서 떨어지는 떡

달나라에는 $N$마리의 토끼가 살고 있다. 달나라는 $N$개의 정점과 $N$개의 방향이 있는 간선으로 구성된 그래프이다. 초기에는 정점 $i$에 $i$번 토끼가 위치해있다. 정점 $i$에서 다른 정점을 거치지 않고 직접 이동할 수 있는 정점 $x_i$는 유일하게 존재한다. 정점 $i$에서 정점 $x_i$로 향하는 간선의 길이는 $d_i$이다.

달나라의 토끼는 떡을 무척이나 좋아한다. 평소에 자신이 위치한 정점에서 한 발짝도 움직이지 않는 토끼라도 우주에서 떡이 떨어질 때만은 매우 열심히 이동한다. 달나라에는 $M$개의 떡이 순서대로 떨어진다. $i$번째 떡은 정점 $v_i$에 떨어진다. 모든 토끼가 떡이 떨어진 정점 $v_i$로 이동하고 싶지만 간선에는 방향이 있기 때문에 정점 $v_i$에 도달 가능한 토끼만이 정점 $v_i$로 이동한다. 정점 $v_i$에 도달하지 못하는 토끼는 자신이 위치한 정점에서 움직이지 않는다.

토끼는 떡이 떨어진 정점에 최대한 빠르게 도착하기 위해 항상 최단 경로를 따라 이동한다. 최단 경로의 길이가 같아도 경로를 이동하는데 필요한 점프 횟수는 토끼마다 다를 수 있다. $i$번 토끼가 길이 $1$만큼 이동하려면 $r_i$번의 점프가 필요하다. $i$번 토끼가 길이가 $l$인 경로를 따라 이동한다면 $r_{i}l$번 점프를 해야한다.

우주에서 떡이 떨어지고 토끼가 이동하는 과정이 반복된다. 떡이 떨어진 정점으로 이동을 마친 토끼는 도착한 정점에서 다음 떡이 떨어질 때까지 기다린다. 떡이 떨어진 정점에 가장 늦게 도착하는 토끼까지 이동을 끝마친 후에 다음 떡이 떨어진다. 더 이상 떨어질 떡이 없으면 과정은 종료된다.

첫 번째 떡이 떨어진 시점부터 마지막 떡이 떨어지고 이동이 마무리 된 시점까지 $i$번 토끼가 점프한 횟수를 $a_i$라고 한다. $a_1,a_2,\cdots ,a_N$을 구하시오.

첫 번째 줄에 $N$이 주어진다. $(2\le N\le 2\times 10^5)$

다음 $N$개의 줄에 $x_i,d_i$가 공백으로 구분되어 주어진다. $(1\le x_i\le N;$ $i\neq x_i;$ $1\le d_i\le 10^5)$

$N+2$ 번째 줄에 $r_1,r_2,\cdots ,r_N$이 공백으로 구분되어 주어진다. $(1\le r_i\le 10^3)$

$N+3$ 번째 줄에 $M$이 주어진다. $(1\le M\le 2\times 10^5)$

$N+4$ 번째 줄에 $v_1,v_2,\cdots ,v_M$이 공백으로 구분되어 주어진다. $(1\le v_i\le N)$

입력으로 주어지는 모든 수는 정수이다.

첫 번째 줄부터 $N$ 번째 줄까지 $i$ 번째 줄에 $a_i$를 출력한다.