tl4 | hacker

Proaspăt ieşit de pe băncile facultăţii, Bujorel s-a decis că cea mai bună meserie pe care o poate urma este cea de hacker. Astfel, el a dat peste o reţea de N calculatoare, etichetate de la 1 la N, dispuse sub forma unui graf ponderat care este arbore. Fiecare muchie are o pondere, care reprezintă distanţa dintre cele două calculatoare aflate în nodurile muchiei. Distanţa dintre oricare două calculatoare se defineşte ca suma distanţelor de pe lanţul dintre ele.

Înainte de a îşi începe atacul, Bujorel va avea M cerinţe. O cerinţă este de forma unei perechi (x, p), unde x reprezintă indicele unui calculator din arbore, iar p o distanţă. El vrea să determine poziţia de pe o muchie unde poate fi amplasat un nou calculator astfel încât distanţa dintre noul calculator şi calculatorul cu indicele x să fie exact p.

Cerinţă

Pentru a deveni ucenicul lui Bujorel, tu trebuie să răspunzi corect la cele M cerinţe.

Date de intrare

Fişierul de intrare hacker.in conţine pe prima linie N şi M, numărul de calculatoare din reţea, respectiv numărul de întrebări. Următoarele N – 1 linii conţin triplete de forma (x, y, d) reprezentând o legătură directă între calculatorul x şi calculatorul y de distanţă d. Ultimele M linii conţin perechi de forma (x, p) reprezentând cerinţa: “Găsiţi două calculatoare a şi b din arbore între care există o muchie, şi o poziţie k pe muchie, astfel încât suma dintre k şi distanţa de la x la a să fie exact p”.

Date de ieşire

Fişierul de ieşire hacker.out va conţine M linii reprezentând răspunsurile la cele M cerinţe. Un răspuns va fi de forma (a, b, k) însemnând că pe muchia dintre calculatoarele a şi b se va amplasa un nou calculator aflat la distanţa k faţă de a.

Restrictii si precizări

• 1 ≤ N, M ≤ 100 000
• 1 ≤ x, y ≤ N
• 1 ≤ d ≤ 64
• Pentru un răspuns de forma (a, b, k), k trebuie să fie în intervalul [0, D(a, b)], unde D(a, b) este distanţa de la calculatorul a la calculatorul b.
• Toate numerele din fişierele de intrare, respectiv de ieşire vor fi numere naturale.
• Se garantează faptul că pentru fiecare întrebare există un răspuns.
• Orice soluţie corectă este acceptată.

Exemplu

hacker.in

8 4
1 2 1
1 7 1
7 8 1
2 3 1 
2 4 1
4 5 1
4 6 1
4 3
2 1
2 3
1 3	

hacker.out

7 1 0
1 7 0
8 7 0
6 4 0