Miasto KOI poniosło znaczne straty podczas pandemii COVID-19 i chce dokładnie przygotować się na możliwe przyszłe pandemie. W tym celu zamierza zbadać podatność obecnej struktury miasta na wirusa.

Miasto KOI składa się z $N$ miejsc i $N-1$ dwukierunkowych dróg, a między dowolnymi dwoma różnymi miejscami można przemieszczać się wyłącznie drogami. Sieć dróg jest więc drzewem. Miejsca mają różne całkowite numery od $0$ do $N-1$. Ponieważ sieć jest drzewem, prosta ścieżka z miejsca $u$ do miejsca $v$ jest jednoznaczna. Odległość między $u$ i $v$ definiujemy jako liczbę krawędzi tej ścieżki.

W mieście KOI mieszka $M$ osób. Dla każdego $0\le j\le M-1$ osoba $j$ mieszka w miejscu $P[j]$ i może odwiedzać miejsca odległe od niego o co najwyżej $D[j]$.

Miejscy wirusolodzy modelują zakażenie między dwiema osobami następująco. Dla każdego $0\le v\le N-1$ miejsce $v$ ma dodatni całkowity czas transmisji $C[v]$. Załóżmy, że osoba $j$ pierwszy raz zakaziła się w chwili $t$, i rozważmy zakażenie osoby $k$. Jeśli obie mogą odwiedzać miejsce $w$, czyli jego odległość od $P[j]$ nie przekracza $D[j]$, a od $P[k]$ nie przekracza $D[k]$, to $w$ jest miejscem pośredniczącym w transmisji.

Jeśli nie ma miejsca pośredniczącego, osoba $k$ nie zakazi się bezpośrednio od $j$, choć zakażenie pośrednie przez inne osoby jest możliwe. W przeciwnym razie niech $x$ będzie miejscem pośredniczącym o najmniejszym czasie transmisji. Jeśli w chwili $t+C[x]$ osoba $k$ nie jest jeszcze zakażona, osoba $j$ zakaża ją w tej chwili. Wirus rozprzestrzenia się tak dla wszystkich par różnych osób $0\le j,k\le M-1$, $j\ne k$.

W tym modelu badacze chcą ustalić chwile zakażenia pozostałych osób, gdy osoba $0$ zakaża się w chwili $0$. Dla każdego $0\le j\le M-1$ oblicz chwilę pierwszego zakażenia osoby $j$. Zapisz $-1$, jeśli nigdy się nie zakazi.

Szczegóły implementacji

Zaimplementuj następującą funkcję.

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$: liczba miejsc w mieście KOI.
• $M$: liczba osób w mieście KOI.
• $A,B$: tablice długości $N-1$. Dla każdego $0\le i\le N-2$ droga łączy miejsca $A[i]$ i $B[i]$. Każda droga występuje w tych tablicach dokładnie raz.
• $P,D$: tablice długości $M$. Dla każdego $0\le j\le M-1$ osoba $j$ mieszka w $P[j]$ i może odwiedzać miejsca odległe od niego o co najwyżej $D[j]$.
• $C$: tablica długości $N$. Dla każdego $0\le v\le N-1$ czas transmisji w miejscu $v$ wynosi $C[v]$.
• Funkcja musi zwrócić tablicę $T$ rozmiaru $M$. Dla każdego $0\le j\le M-1$ element $T[j]$ ma być chwilą pierwszego zakażenia osoby $j$ albo $-1$, jeśli nigdy się nie zakazi.
• Funkcja jest wywoływana dokładnie raz na przypadek testowy.

W żadnym miejscu przesłanego kodu nie wolno wywoływać funkcji wejścia ani wyjścia.

Ograniczenia

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

Podzadania

1. (5 punktów)

   • $N\le500$, $M\le500$.
   • Dla każdego $0\le i\le N-2$, $A[i]=i$, $B[i]=i+1$.

2. (8 punktów)

   • $N\le5\,000$, $M\le5\,000$.
   • Dla każdego $0\le i\le N-2$, $A[i]=i$, $B[i]=i+1$.

3. (27 punktów)

   • Dla każdego $0\le i\le N-2$, $A[i]=i$, $B[i]=i+1$.

4. (5 punktów)

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

5. (8 punktów)

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

6. (47 punktów)

   • Brak dodatkowych ograniczeń.

Przykład

Przykład 1

Rozważmy przypadek, w którym $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]$.

Sprawdzarka wywołuje funkcję następująco.

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])

W tym przypadku wirus rozprzestrzenia się następująco.

• Osoba $0$ zakaża się w chwili $0$.
• Osoba $3$ zakaża się w chwili $5$ od osoby $0$, za pośrednictwem miejsca $1$. (Miejsce $2$ również może pośredniczyć.)
• Osoba $4$ zakaża się w chwili $16$ od osoby $0$, za pośrednictwem miejsca $3$.
• Osoba $1$ zakaża się w chwili $24$ od osoby $4$, za pośrednictwem miejsca $5$.
• Osoba $2$ nigdy się nie zakaża.

Funkcja powinna zwrócić $[0,24,-1,5,16]$.

Przykład 2

Sprawdzarka wywołuje funkcję następująco.

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])

Funkcja powinna zwrócić $[0,24,10,5,16]$.

Przykład 3

Sprawdzarka wywołuje funkcję następująco.

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])

Funkcja powinna zwrócić $[0,11,17,11,5,11,5,11,17,5]$.

Przykład 4

Sprawdzarka wywołuje funkcję następująco.

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

Funkcja powinna zwrócić $[0,1000000000]$.

Przykładowa sprawdzarka

Przykładowa sprawdzarka odczytuje wejście w następującym formacie.

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

Przykładowa sprawdzarka wypisuje:

• Wiersz $1+j\quad(0\le j\le M-1)$: element o indeksie $j$ tablicy zwróconej przez find_spread.

Przykładowa sprawdzarka może różnić się od sprawdzarki używanej do właściwego oceniania.