Fișierul intrare/ieșire	flota.in, flota.out	Sursă	ad-hoc
Autor	Cătălin Frâncu	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	1.5 sec	Limită de memorie	10240 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Flota

Mândria complexului de agrement de la Șmenu sunt plimbările cu vaporul pe salba de N lacuri legate prin M canale. Un vapor de lățime L poate naviga între două lacuri dacă există o cale între cele două lacuri formată numai din canale de lățime cel puțin egală cu L. Proprietarul complexului, Trăiam Binescu, dorește să cumpere o flotă de vapoare, toate identice, care să deservească toate lacurile. Deoarece prețurile variază pentru vapoare de diverse lățimi, Binescu își notează K lățimi și dorește să afle, în fiecare caz, numărul minim de vapoare necesare.

Date de intrare

Fișierul de intrare flota.in conține, pe prima linie, numerele N, M și K.

Următoarele M linii conțin triplete de numere x y w, semnificând că între lacurile x și y există un canal de lățime w.

Ultimele K linii conțin câte un număr L _i, semnificând o posibilă lățime a vapoarelor de cumpărat.

Date de ieșire

În fișierul de ieșire flota.out se vor scrie K linii. Linia i va conține un singur număr, respectiv numărul de vapoare care sunt necesare pentru lățimea L _i. Răspunsurile trebuie afișate în aceeași ordine cu întrebările.

Restricții

• 1 ≤ N ≤ 50.000
• 1 ≤ M ≤ 1.000.000
• 1 ≤ K ≤ 100.000
• Între oricare două lacuri există cel mult un canal. Toate canalele au dublu sens.
• Lățimile canalelor și ale vapoarelor sunt întregi, pozitive, cel mult egale cu 50.000.

Exemplu