Fişierul intrare/ieşire:	sate.in, sate.out	Sursă	preONI 2007 Runda Finala
Autor	Filip Cristian Buruiana	Adăugată de	Filip Cristian Buruiana •filipb
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sate

Intr-o tara pitoreasca, intr-un judet de munte, sunt N sate coliniare numerotate cu numere naturale de la 1 la N. La ultima conferinta a cartografilor a fost pusa in discutie tocmai dispunerea acestor sate. La conferinta au participat exact M cartografi. Fiecare cartograf, in ordine, de la 1 la M, cand ia discursul, fie prezinta o noua descoperire, fie pune o intrebare despre dispunerea satelor. Astfel, cartograful cu numarul de ordine k urmeaza dupa primii k-1 cartografi si poate:

• sa precizeze distanta dintre satele i si j (i < j). Distanta este un numar natural si este exprimata in kilometri
• sa intrebe care este distanta intre satele i si j (i < j). Raspunsul ii va fi dat de un program care tine cont de toate descoperirile cartografilor care au luat cuvantul inaintea sa. Daca distanta nu poate fi determinata conform indiciilor existente pana in prezent, programul va returna valoarea -1.

Sa se determine raspunsul dat de program fiecarui cartograf care pune o intrebare.

Date de intrare

Pe prima linie a fisierului sate.in se afla N si M, unde N este numarul de sate si M este numarul de cartografi. Pe fiecare din urmatoarele M linii se gaseste descrierea actiunii unui cartograf. Astfel, daca primul numar de pe linie este 0, atunci cartograful curent a realizat o noua descoperire. Pe aceeasi linie urmeaza 3 numere naturale i j D, indicand faptul ca distanta dintre satele i si j (i < j) este de D kilometri. Daca primul numar de pe linie este 1, atunci cartograful curent pune o intrebare. Urmeaza pe aceeasi linie doua numere i si j (i < j). Programul automat ii va raspunde cu distanta dintre satele i si j folosind toate informatiile existente pana in prezent sau cu -1, daca aceasta distanta nu poate fi determinata.

Date de iesire

Fisierul de iesire sate.out contine, in ordine, raspunsurile date cartografilor care au pus intrebari, cate un raspuns pe linie.

Restrictii

• 1 ≤ N ≤ 400
• 1 ≤ M ≤ 2048
• Relatiile descoperite de cartografi nu sunt contradictorii
• Se garanteaza ca distanta intre satele 1 si N nu depaseste 20 de milioane

Exemplu

Cum se trimit solutii?