Koi City Virus

Because KOI City suffered significant damage during the recent COVID-19 pandemic, the city is determined to thoroughly prepare for any future pandemic situations. To this end, KOI City aims to analyze how vulnerable its current urban structure is to viruses.

KOI City consists of $N$ locations and $N - 1$ bidirectional roads, allowing any two different locations to be reached using only the roads. In other words, the city's road network forms a tree structure. Each location is identified by a unique integer between $0$ and $N - 1$. Since the city's road network is a tree, for any two locations $u$ and $v$, there is a unique simple path from location $u$ to location $v$. The number of edges on this unique path is defined as the distance between $u$ and $v$.

There are $M$ people living in KOI City. For each $j$ (where $0 ≤ j ≤ M - 1$), person $j$ lives at location $P[j]$ and can travel to any location within a distance of $D[j]$ from that location.

KOI City's virologists have modeled the process of virus transmission between two people as follows. For every $v$ (where $0 ≤ v ≤ N - 1$), the transmission time at location $v$ is represented by a positive integer $C[v]$. Suppose person $j$ is initially infected by the virus at time $t$, and the person who might get infected from person $j$ is person $k$. If there is a location $w$ that both person $j$ and person $k$ can reach—meaning the distance between location $w$ and $P[j]$ is at most $D[j]$, and the distance between location $w$ and $P[k]$ is at most $D[k]$—then location $w$ becomes a medium for transmission.

If no such medium location exists, person $k$ will not be directly infected by person $j$ (though they may still be infected indirectly through another person). If a medium location does exist, let $x$ be the location among them with the minimum transmission time. If person $k$ is not infected by time $t + C[x]$, then they will be infected by person $j$ at that time. The virus spreads in this way for all different pairs of people $0 ≤ j, k ≤ M - 1$, where $j \ne k$.

Under this model, the researchers in KOI City want to calculate when the other people will get infected if person $0$ is infected at time $0$. You need to calculate the time at which each person $j$ (for all $0 ≤ j ≤ M - 1$) is first infected by the virus. If person $j$ is never infected, the time should be recorded as $-1$.