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 lungime 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.
Restricţii
• 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ă.