• محدودیت زمان: ۴ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

علی که در این گرمای تابستان اعضای شرکت را به اسکیپ روم برده بود برای رفع خستگی تصمیم می‌گیرد برای آن‌ها نوشابه بخرد... اما می‌خواهد تنها برای افرادی نوشابه بخرد که بتوانند سوالات زیر را درباره گراف پاسخ دهند...

فرض کنید \(G\) یک گراف وزن دار بدون جهت همبند باشد. \(G\) دارای \(n\) راس و \(m\) یال است. هر یال \(G\) دو راس مختلف را به هم متصل می‌کند.

همچنین راس‌های این گراف با ۱ تا \(n\) شماره گذاری شده‌اند. روی راس شماره \(i\) عدد \(a_i\) نوشته شده است.

از ما تعدادی سوال پرسیده می‌شود. در هر سوال سه عدد \(v\) و \(x\) و \(k\) داده می‌شود و از ما کوچک‌ترین مقدار \(w\) را می‌خواهند که حداقل \(k\) راس وجود داشته باشند که فاصله آن‌ها از \(v\) فاصله حداکثر \(w\) باشد و عدد نوشته شده روی آن نسبت به \(x\) اول باشد.

منظور از وزن یک مسیر بزرگ ترین عددی است که روی یال‌های آن مسیر وجود دارد.

منظور از فاصله دو راس مانند \(u\) و \(v\) کمینه مقدار وزن تمام مسیرهای ممکن بین \(u\) و \(v\) است.

ورودی

در سطر اول ورودی سه عدد طبیعی \(n\) و \(m\) و\(q\) با فاصله از هم آمده است که به ترتیب نشان دهنده تعداد رئوس، یال‌ها و سوالاتی است که باید به آن‌ها پاسخ بدهیم. \[1 \le n, m, q \le 100\ 000\] در سطر دوم \(n\) عدد مانند \(a_1, a_2, a_3,..., a_n\) با فاصله آمده که نشان دهنده اعداد نوشته شده روی رئوس گراف است.

در \(i\)امین سطر از \(m\) سطر بعدی، سه عدد \(v_i\) و \(u_i\) و \(w_i\) عدد آمده است که نشان‌دهنده وجود یالی با وزن \(w_i\) بین دو راس \(v_i\) و \(u_i\) است. دقت کنید که لزومی ندارد گراف ساده باشد و ممکن است طوقه یا یال چندگانه داشته باشیم. \[1 \le u_i, v_i \le n\] \[1 \le w_i \le 10^9 \]

در \(j\)امین سطر از \(q\) سطر بعدی، سه عدد \(v_j\) و \(x_j\) و \(k_j\) آمده است که نشان دهنده سوال علی از شماست؟\[1 \le a_i, x_j \le 500\ 000\] \[1 \le v_j \le n\] \[2 \le k_j \le n\]

خروجی

در \(q\) سطر خروجی در سطر \(i\)ام پاسخ سوال \(i\)ام را چاپ کنید.

مثال

ورودی نمونه ۱

3 3 2
6 9 5
1 2 10
2 3 20
1 3 30
3 7 2
1 25 2

خروجی نمونه ۱

20
10

ورودی نمونه ۲

4 3 4
1 2 3 4
1 2 10
2 3 1
3 4 2
3 3 2
4 5 3
4 5 4
1 2 4

خروجی نمونه ۲

2
2
10
-1