copacsmenar

Copac Smenar

== include(page="template/taskheader" task_id="copacsmenar") ==

Andrei asculta melodiile lui Bob Marley si astfel afla despre miscarea Rastafari. Impresionat, decide sa-si creeze propria religie. Din miscarea Rastafari, va prelua doar o singura parte care i-a placut cel mai mult. De asemenea, tot atunci devine si administratorul infoarena.ro, careia, in mod nesurprinzator, ii alege culoarea verde.

Andrei asculta melodiile lui Bob Marley si astfel afla despre miscarea Rastafari. Impresionat, decide sa-si creeze propria religie. Din miscarea Rastafari, va prelua doar o singura parte care i-a placut cel mai mult. De asemenea, tot atunci devine si administratorul infoarena.ro, careia, in mod nesurprinzator, ii alege culoarea verde. Tot atunci creeaza o lista cu problemele importante ale site-ului, unele idei din acea lista fiind relevante chiar si in zilele noastre.

Tanarul Rastaman vrea sa gaseasca un ritual de initiere pentru elevii sai, pentru a afla daca sunt demni de a fi parte a cultului. Astfel, un tanar pe cale de a fi initiat este dus in Templul Smecheriei, la Copacul Smenar. Copacul poate fi privit ca un arbore cu n noduri, cu costuri pe muchii. Radacina arborelui este nodul 1.

Andrei da m restrictii de forma (x, y, valmin, valmax): distanta intre nodul x si y este cuprinsa intre valmin si valmax. Apoi, urmeaza q query-uri de forma (A, B): Pentru o pereche (A, B) data de Andrei, sunt toate cele m restrictii indeplinite? Raspundeti corect la cele q query-uri pentru o viata mai verde.

Input
 
n m q
n - 1 linii ce descriu arborele de forma x y c: exista o muchie intre x si y de cost c
m linii ce descriu restrictiile de forma x y valmin valmax : distanta dintre nodurile x si y e cuprinsa intre valmin si valmax
q linii de forma a b: un query pt perechea (A, B)
 
Output
 
q linii: pentru fiecare query afisaza 1 daca perechea respecta toate restrictiile si 0 altfel.
 
Restrictii
 
nodul 1 e radacina arborelui
n intre 1 si 50
m intre 0 si n * (n - 1) / 2
q intre 1 si 100000
costurile pe muchii numere intregi in val abs pana in 10^3
valmin si valmax  numere intregi in val abs pana in 10^7
 

h2. Date de intrare
Fişierul de intrare $copacsmenar.in$ contine pe prima linie numerele n, m si q. Pe cea de-a doua linie este data descrierea arborelui prin intermediul a 3 numere: x, y si c, reprezentand ca exista o muchie intre x si y de cost c. Urmatoarele m linii descriu restrictiile prin 4 numere: x, y, valmin, valmax, semnificand ca distanta intre nodul x si y este cuprinsa intre valmin si valmax. Urmatoarele q linii descriu query-urile, printr-o pereche de numere (A, B).

h2. Restricţii
* $1 ≤ n ≤ 50$

* $1 ≤ m ≤ n*(n-1)/2$

* $1 ≤ m ≤ n*(n-1)$

* $1 ≤ q ≤ 100000$
* Costurile muchiior sunt numere intregi care, in valoare absoluta nu depasesc 1000.
* Valorile lui valmin si valmax sunt numere intregi care, in valoare absoluta nu depasesc $10^7$.

* Valorile lui A si B din query-uri sunt numere intregi care, in valoare absoluta nu depasesc $10^7$.
* Perechile ordonate (x, y) din cele m restrictii sunt distincte 2 cate 2, iar x != y.
* In ciuda restrictiei specifice a lui n, problema nu are nicio legatura cu plaforma TopCoder :(

h2. Exemplu