KOI 市は新型コロナウイルスの大流行で大きな被害を受けたため、今後起こり得るパンデミックに十分に備えようとしています。そのため、現在の都市構造がウイルスに対してどの程度脆弱かを分析したいと考えています。

KOI 市は $N$ 個の地点と $N-1$ 本の双方向道路からなり、異なる任意の 2 地点間を道路だけで移動できます。つまり道路網は木です。地点には $0$ から $N-1$ の異なる整数の番号が付いています。道路網が木なので、地点 $u$ から地点 $v$ への単純パスは一意です。このパスの辺数を $u$ と $v$ の距離と定義します。

KOI 市には $M$ 人が住んでいます。すべての $0\le j\le M-1$ について、人 $j$ は地点 $P[j]$ に住み、そこからの距離が $D[j]$ 以下の地点へ行けます。

市のウイルス学者は、2 人の間の感染を次のようにモデル化しました。すべての $0\le v\le N-1$ について、地点 $v$ の感染伝播時間は正の整数 $C[v]$ です。人 $j$ が時刻 $t$ に初めて感染したとし、人 $k$ への伝播を考えます。地点 $w$ に両者が行ける、すなわち $w$ と $P[j]$ の距離が $D[j]$ 以下、$w$ と $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]$ を結ぶ道路があります。各道路はこの 2 配列にちょうど 1 回現れます。
• $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$ について、$T[j]$ は人 $j$ が初めて感染する時刻であり、感染しない場合は $-1$ でなければなりません。
• この関数は各テストケースでちょうど 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$ が感染します。
• 時刻 $5$ に人 $3$ が人 $0$ から感染し、媒介地点は $1$ です。（地点 $2$ も媒介地点になれます。）
• 時刻 $16$ に人 $4$ が人 $0$ から感染し、媒介地点は $3$ です。
• 時刻 $24$ に人 $1$ が人 $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$ の要素。

サンプル採点プログラムは実際の採点プログラムと異なる場合があります。