A cidade KOI sofreu grandes danos durante a pandemia de COVID-19 e deseja se preparar cuidadosamente para possíveis pandemias futuras. Para isso, pretende analisar a vulnerabilidade de sua estrutura atual a um vírus.

A cidade KOI consiste em $N$ locais e $N-1$ estradas bidirecionais, e é possível viajar entre quaisquer dois locais distintos usando apenas estradas. Assim, sua rede de estradas é uma árvore. Os locais têm rótulos inteiros distintos de $0$ a $N-1$. Como a rede é uma árvore, existe um único caminho simples de um local $u$ a um local $v$. A distância entre $u$ e $v$ é definida como o número de arestas desse caminho.

Existem $M$ pessoas na cidade KOI. Para todo $0\le j\le M-1$, a pessoa $j$ mora em $P[j]$ e pode visitar locais cuja distância dali seja no máximo $D[j]$.

Os virologistas da cidade modelam a transmissão entre duas pessoas assim. Para todo $0\le v\le N-1$, o local $v$ tem um tempo de transmissão inteiro positivo $C[v]$. Suponha que a pessoa $j$ se infecte pela primeira vez no instante $t$ e considere a transmissão à pessoa $k$. Se ambas podem visitar o local $w$, isto é, sua distância de $P[j]$ é no máximo $D[j]$ e de $P[k]$ é no máximo $D[k]$, então $w$ é um local intermediário de transmissão.

Se não houver local intermediário, a pessoa $k$ não será infectada diretamente por $j$, embora possa ser infectada indiretamente por outras pessoas. Caso contrário, seja $x$ um local intermediário com tempo mínimo de transmissão. Se a pessoa $k$ ainda não estiver infectada no instante $t+C[x]$, a pessoa $j$ a infecta nesse instante. O vírus se espalha assim para todos os pares de pessoas distintas $0\le j,k\le M-1$, $j\ne k$.

Nesse modelo, os pesquisadores querem saber quando os demais se infectam se a pessoa $0$ se infectar no instante $0$. Para todo $0\le j\le M-1$, calcule o instante da primeira infecção da pessoa $j$. Registre $-1$ se ela nunca se infectar.

Detalhes de implementação

Você deve implementar a função a seguir.

vector<long long> find_spread(int N, int M, vector<int> A, vector<int> B,
vector<int> P, vector<int> D, vector<int> C)

• $N$: quantidade de locais na cidade KOI.
• $M$: quantidade de pessoas na cidade KOI.
• $A,B$: vetores de comprimento $N-1$. Para todo $0\le i\le N-2$, uma estrada conecta $A[i]$ a $B[i]$. Cada estrada aparece exatamente uma vez nesses dois vetores.
• $P,D$: vetores de comprimento $M$. Para todo $0\le j\le M-1$, a pessoa $j$ mora em $P[j]$ e pode visitar locais a uma distância dali de no máximo $D[j]$.
• $C$: vetor de comprimento $N$. Para todo $0\le v\le N-1$, o tempo de transmissão no local $v$ é $C[v]$.
• A função deve retornar um vetor $T$ de tamanho $M$. Para todo $0\le j\le M-1$, $T[j]$ deve ser o primeiro instante de infecção da pessoa $j$, ou $-1$ se ela nunca se infectar.
• A função é chamada exatamente uma vez por caso de teste.

Você não deve chamar funções de entrada ou saída em nenhuma parte do código-fonte enviado.

Restrições

• $1\le N\le100\,000$
• $1\le M\le100\,000$
• Para todo $0\le i\le N-2$, $0\le A[i],B[i]\le N-1$, $A[i]\ne B[i]$.
• Para todo $0\le j\le M-1$, $0\le P[j],D[j]\le N-1$.
• Para todo $0\le v\le N-1$, $1\le C[v]\le10^9$.

Subtarefas

1. (5 pontos)

   • $N\le500$, $M\le500$.
   • Para todo $0\le i\le N-2$, $A[i]=i$, $B[i]=i+1$.

2. (8 pontos)

   • $N\le5\,000$, $M\le5\,000$.
   • Para todo $0\le i\le N-2$, $A[i]=i$, $B[i]=i+1$.

3. (27 pontos)

   • Para todo $0\le i\le N-2$, $A[i]=i$, $B[i]=i+1$.

4. (5 pontos)

   • $N\le500$, $M\le500$.

5. (8 pontos)

   • $N\le5\,000$, $M\le5\,000$.

6. (47 pontos)

   • Sem restrições adicionais.

Exemplos

Exemplos 1

Considere o caso em que $N=8$, $M=5$, $A=[0,1,2,3,4,5,6]$, $B=[1,2,3,4,5,6,7]$, $P=[2,5,7,1,4]$, $D=[2,0,0,1,1]$, $C=[40,5,5,16,32,8,1,10]$.

O avaliador chama a função da seguinte maneira.

find_spread(8, 5, [0, 1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6, 7], [2, 5, 7, 1,
4], [2, 0, 0, 1, 1], [40, 5, 5, 16, 32, 8, 1, 10])

Nesse caso, o vírus se espalha da seguinte maneira.

• A pessoa $0$ se infecta no instante $0$.
• A pessoa $3$ se infecta no instante $5$, pela pessoa $0$, usando o local $1$ como intermediário. (O local $2$ também pode ser intermediário.)
• A pessoa $4$ se infecta no instante $16$, pela pessoa $0$, usando o local $3$ como intermediário.
• A pessoa $1$ se infecta no instante $24$, pela pessoa $4$, usando o local $5$ como intermediário.
• A pessoa $2$ nunca se infecta.

A função deve retornar $[0,24,-1,5,16]$.

Exemplos 2

O avaliador chama a função da seguinte maneira.

find_spread(8, 5, [0, 1, 2, 3, 4, 3, 3], [1, 2, 3, 4, 5, 6, 7], [2, 5, 7, 1,
4], [2, 0, 0, 1, 1], [40, 5, 5, 16, 32, 8, 1, 10])

A função deve retornar $[0,24,10,5,16]$.

Exemplos 3

O avaliador chama a função da seguinte maneira.

find_spread(10, 10, [9, 0, 1, 5, 3, 8, 0, 6, 0], [3, 6, 8, 1, 2, 7, 4, 5, 9],
[9, 7, 1, 8, 6, 1, 4, 7, 5, 5], [0, 2, 0, 1, 3, 2, 6, 2, 1, 4], [10, 12, 5, 9,
8, 21, 20, 6, 13, 5])

A função deve retornar $[0,11,17,11,5,11,5,11,17,5]$.

Exemplos 4

O avaliador chama a função da seguinte maneira.

find_spread(1, 2, [], [], [0, 0], [0, 0], [1000000000])

A função deve retornar $[0,1000000000]$.

Avaliador de exemplo

O avaliador de exemplo lê a entrada no formato a seguir.

• Linha $1$: $N\ M$.
• Linha $2+i\quad(0\le i\le N-2)$: $A[i]\ B[i]$.
• Linha $1+N+j\quad(0\le j\le M-1)$: $P[j]\ D[j]$.
• Linha $1+N+M$: $C[0]\ C[1]\ \ldots\ C[N-1]$.

O avaliador de exemplo imprime o seguinte.

• Linha $1+j\quad(0\le j\le M-1)$: o elemento de índice $j$ do vetor retornado por find_spread.

Observe que o avaliador de exemplo pode ser diferente daquele usado na avaliação real.