KOI 城市在新冠疫情中遭受了很大損失，希望為未來可能發生的大流行做好充分準備。因此，KOI 城市希望分析目前的城市結構對病毒的脆弱程度。

KOI 城市由 $N$ 個地點和 $N-1$ 條雙向道路組成，任意兩個不同地點都可以僅透過道路往返。因此，城市的道路網路構成一棵樹。各地點用從 $0$ 到 $N-1$ 的不同整數編號。由於道路網路是一棵樹，從地點 $u$ 到地點 $v$ 的簡單路徑唯一。定義 $u$ 與 $v$ 的距離為這條路徑上的邊數。

KOI 城市中住著 $M$ 個人。對於所有 $0\le j\le M-1$，第 $j$ 個人住在地點 $P[j]$，可以前往與該地點距離不超過 $D[j]$ 的地點。

城市的病毒學家如下建立兩個人之間的病毒傳播模型。對於所有 $0\le v\le N-1$，地點 $v$ 的傳播時間為正整數 $C[v]$。假設第 $j$ 個人在時刻 $t$ 首次感染，考慮其向第 $k$ 個人傳播病毒。如果兩個人都能前往地點 $w$，即 $w$ 到 $P[j]$ 的距離不超過 $D[j]$、到 $P[k]$ 的距離不超過 $D[k]$，那麼地點 $w$ 就是一個傳播媒介。

如果不存在傳播媒介地點，第 $k$ 個人不會被第 $j$ 個人直接感染，但仍可能透過其他人間接感染。否則，設 $x$ 是所有媒介地點中傳播時間最小的一個地點。如果第 $k$ 個人在時刻 $t+C[x]$ 尚未感染，則會在該時刻被第 $j$ 個人感染。對於所有不同的人組成的數對 $0\le j,k\le M-1$、$j\ne k$，病毒均按這種方式傳播。

在上述模型下，研究人員想計算當第 $0$ 個人在時刻 $0$ 感染時，其他人會在何時感染。對於所有 $0\le j\le M-1$，你需要計算第 $j$ 個人首次感染的時刻。如果這個人永遠不會感染，則記錄為 $-1$。

實作細節

你需要實作以下函式。

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$：KOI 城市中的地點數量。
• $M$：KOI 城市中的人數。
• $A,B$：長度為 $N-1$ 的陣列。對於所有 $0\le i\le N-2$，有一條道路連接地點 $A[i]$ 和 $B[i]$。每條道路在這兩個陣列中恰好出現一次。
• $P,D$：長度為 $M$ 的陣列。對於所有 $0\le j\le M-1$，第 $j$ 個人住在地點 $P[j]$，可以前往與其距離不超過 $D[j]$ 的地點。
• $C$：長度為 $N$ 的陣列。對於所有 $0\le v\le N-1$，地點 $v$ 的傳播時間為 $C[v]$。
• 函式應回傳一個長度為 $M$ 的陣列 $T$。對於所有 $0\le j\le M-1$，如果第 $j$ 個人會感染，則 $T[j]$ 為其首次感染時刻，否則為 $-1$。
• 每個測試案例只呼叫此函式一次。

提交的原始碼中的任何位置都不得呼叫輸入輸出函式。

資料範圍

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

子任務

1. (5 分)

   • $N\le500$, $M\le500$.
   • 對於所有 $0\le i\le N-2$， $A[i]=i$, $B[i]=i+1$.

2. (8 分)

   • $N\le5\,000$, $M\le5\,000$.
   • 對於所有 $0\le i\le N-2$， $A[i]=i$, $B[i]=i+1$.

3. (27 分)

   • 對於所有 $0\le i\le N-2$， $A[i]=i$, $B[i]=i+1$.

4. (5 分)

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

5. (8 分)

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

6. (47 分)

   • 沒有額外限制。

範例

範例 1

考慮以下情況： $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]$.

評分程式如下呼叫函式。

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

此時病毒按以下方式傳播。

• 第 $0$ 個人在時刻 $0$ 感染。
• 第 $3$ 個人在時刻 $5$ 被第 $0$ 個人感染，傳播媒介為地點 $1$。（地點 $2$ 也可以作為傳播媒介。）
• 第 $4$ 個人在時刻 $16$ 被第 $0$ 個人感染，傳播媒介為地點 $3$。
• 第 $1$ 個人在時刻 $24$ 被第 $4$ 個人感染，傳播媒介為地點 $5$。
• 第 $2$ 個人始終不會感染。

函式應回傳 $[0,24,-1,5,16]$.

範例 2

評分程式如下呼叫函式。

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

函式應回傳 $[0,24,10,5,16]$.

範例 3

評分程式如下呼叫函式。

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

函式應回傳 $[0,11,17,11,5,11,5,11,17,5]$.

範例 4

評分程式如下呼叫函式。

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

函式應回傳 $[0,1000000000]$.

範例評分程式

範例評分程式按以下格式讀入輸入。

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

範例評分程式輸出以下內容。

• 行 $1+j\quad(0\le j\le M-1)$: 函式 find_spread 回傳陣列中索引為 $j$ 的元素。

注意，範例評分程式可能與實際評分使用的評分程式不同。