Fişierul intrare/ieşire:	termite.in, termite.out	Sursă	Lot Vaslui 2014 Seniori Baraj 4
Autor	Andrei Ciocan, Andrei Parvu	Adăugată de	Marian Darius •dariusdarius
Timp execuţie pe test	0.575 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Termite

În lipsa prinţesei cu ochii verzi, tărâmul ei fermecat a fost invadat de termite! Se ştie despre tărâmul fermecat că este organizat sub forma unui graf conex neorientat, în care fiecare muchie are atribuită o lungime. Prinţesa nu poate să combată această invazie, însă ea a aflat informaţii preţioase despre aceste termite. Se ştie că invazia a pornit simultan din exact K noduri, la un moment de timp pe care îl vom nota cu 0. Aceste termite, o dată aflate într-un nod, îl manâncă instant, se înmultesc şi pornesc pe muchiile incidente nodului către nodurile vecine. Astfel, dacă o termită ajunge într-un nod la un moment de timp T, tot în acelaşi moment termitele îl vor mânca, se vor înmulţi şi vor porni către celelalte noduri. Prinţesa mai ştie de altfel că timpul lor de deplasare este constant şi că acestea parcurg o muchie de lungime L exact în L secunde. Un nod o dată mâncat, acesta va dispărea din graf, însă nu neapărat şi muchiile incidente lui (muchia va ramâne în graf atâta timp cât este incidentă cel puţin unui nod). Altfel zis, o muchie va dispărea doar atunci când ambele noduri de la capete ei vor fi mâncate.
Prinţesa nu îşi poate salva întregul regat, însă ar dori să ştie dacă ar putea salva unele comori care se află în anumite noduri ale grafului. Astfel, ea va va pune Q întrebări de forma A B T cu următoarea semnificaţie: ştiind că prinţesa se află la momentul T în nodul A, iar comoara se află în nodul B, câte secunde se vor scurge până când nu va mai exista niciun drum între ea şi comoară (aceasta se poate întampla şi în cazurile în care nodul A sau nodul B este mâncat). Dacă încă din momentul T nu există niciun drum între cele două noduri, atunci se va afişa 0.

Cerinta

Ajutaţi-o pe prinţesă, raspunzând corect la toate cele Q întrebari.

Date de intrare

Fişierul de intrare termite.in conţine pe prima linie 4 numere naturale: n – numărul de noduri ale grafului, m - numărul de muchii ale grafului, k – numărul de noduri din care au pornit termitele şi Q – numărul de întrebări. A doua linie a fişierului va conţine k valori, semnificând indicele nodurilor unde au apărut în momentul 0 termitele. Următoarele m linii vor conţine cate 3 valori : a, b şi L, însemnând că între nodurile a şi b există o muchie de lungime L. Următoarele Q linii din fişierul de intrare vor reprezenta query-urile, în forma A B T, însemnand câte secunde mai are prinţesa începând de la momentul de timp T până când nu va mai exista drum între nodurile A şi B.

Date de ieşire

Fişierul de iesire termite.out va conţine Q linii cu câte un singur număr natural reprezentând răspunsurile la cele Q întrebari.

Restricţii

• 1 ≤ n, k ≤ 300 000
• 1 ≤ m, Q ≤ 400 000

Exemplu

Cum se trimit solutii?