تعرضت مدينة KOI لأضرار كبيرة خلال جائحة كوفيد-19، ولذلك تريد الاستعداد جيدًا لأي جائحة محتملة مستقبلًا. ولهذا الغرض، تريد تحليل مدى تأثر بنيتها الحالية بانتشار فيروس.

تتكون مدينة 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$، أي إن مسافته عن $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]$.
• يجب أن تعيد الدالة مصفوفة $T$ حجمها $M$. لكل $0\le j\le M-1$، يجب أن يكون $T[j]$ زمن الإصابة الأولى للشخص $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)$: العنصر ذو الفهرس $j$ من المصفوفة التي تعيدها find_spread.

لاحظ أن برنامج التقييم التجريبي قد يختلف عن برنامج التقييم الفعلي.