바이러스

KOI 도시는 지난 코로나19 대유행으로 많은 피해를 겪었기 때문에, 향후 발생할 수 있는 팬데믹 상황에 철저히 대비하려고 한다. 이를 위해, KOI 도시는 현재의 도시 구조가 바이러스에 어느 정도로 취약한지를 분석하고자 한다.

KOI 도시는 $N$개의 지점과 $N - 1$개의 양방향 도로로 이루어져 있으며, 임의의 서로 다른 두 지점을 도로만을 사용하여 오갈 수 있다. 즉, 도시의 도로망은 트리 구조를 이룬다. 각 지점은 $0$ 이상 $N - 1$ 이하의 서로 다른 정수로 구분된다. 도시의 도로망이 트리이기 때문에, 두 지점 $u$, $v$에 대해서, $u$번 지점에서 $v$번 지점으로 이동하는 단순 경로는 유일하다. 이 유일한 경로의 간선의 개수를 $u$와 $v$의 거리 라고 정의하자.

KOI 도시에는 $M$명의 사람들이 살고 있다. 모든 $0 ≤ j ≤ M - 1$에 대해, $j$번 사람은 $P[j]$번 지점에 살고 있으며, 해당 지점에서 거리가 $D[j]$ 이하인 지점을 오갈 수 있다.

KOI 도시의 바이러스학자들은, 두 사람 간에 바이러스가 전파되는 과정을 다음과 같이 모델링하였다. 모든 $0 ≤ v ≤ N - 1$에 대해, $v$번 지점의 전파 시간은 $C[v]$라는 양의 정수로 표현된다. $j$번 사람이 시각 $t$에 처음으로 바이러스에 감염되었다고 하고, $j$번 사람에게서 바이러스를 전파받을 사람을 $k$번 사람이라고 하자. $w$번 지점을 $j$번 사람과 $k$번 사람이 공동으로 오갈 수 있다면 – 다시 말해, $w$번 지점과 $P[j]$번 지점의 거리가 $D[j]$ 이하고 $w$번 지점과 $P[k]$번 지점의 거리가 $D[k]$ 이하라면, $w$번 지점은 전파의 매개체가 된다.

만약에 전파의 매개체가 되는 지점이 없다면, $k$번 사람은 $j$번 사람으로부터 직접 바이러스에 감염되지 않는다. (물론 다른 사람을 통하여 간접적으로 감염될 수는 있다) 전파의 매개체가 되는 지점이 있다면, 그러한 지점 중 전파 시간을 최소화하는 지점의 번호를 $x$라고 하자. $k$번 사람이 만약 시각 $t + C[x]$에 바이러스에 감염되지 않았다면, $k$번 사람은 그 시각에 $j$번 사람에 의해 바이러스에 감염된다. 바이러스는, 모든 서로 다른 사람의 쌍 $0 ≤ j, k ≤ M - 1$, $j \ne k$에 대해 이러한 식으로 확산한다.

위와 같은 모델링 하에서, KOI 도시의 연구진들은 $0$번 사람이 시각 $0$에 바이러스에 감염되었을 때, 다른 사람들이 바이러스에 언제 감염되는지를 계산하려고 한다. 당신은, 모든 $0 ≤ j ≤ M -1$에 대해, $j$번 사람이 처음으로 바이러스에 감염되는 시각을 계산해야 한다. 단, 만약 $j$번 사람이 바이러스에 감염되지 않는다면, 그 시각을 $-1$ 이라고 기록해야 한다.

문제

제한