Cerința

Se dă un arbore cu n noduri, în care fiecare muchie are asociat un număr natural. Se cere răspunsul la Q întrebări de forma: dacă u şi v sunt două noduri din arbore, care este valoarea xor a tuturor numerelor asociate muchiilor situate pe lanţul ce uneşte u şi v?

Date de intrare

Fișierul de intrare arbori_xor.in conține pe prima linie numerele n şi Q, pe următoarele n-1 linii câte o pereche de numere naturale ce reprezintă extremităţile unei muchii din arbore urmată de un număr natural ce reprezintă valoarea muchiei, iar pe următoarele Q linii câte o pereche de numere naturale ce reprezintă nodurile pentru care se cere xor-ul valorilor de pe lanţul ce le uneşte .

Date de ieșire

Fișierul de ieșire arbori_xor.out va conține pe primele Q linii răspunsurile la cele Q cerinţe.

Restricții și precizări

• 2 ≤ n ≤ 10.000
• 1 ≤ Q ≤ 500.000
• valorile asociate muchiilor sunt numere naturale cel mult egale cu 10.000

Exemplu:

arbori_xor.in

5 2
1 2 7
1 3 4
3 4 1
4 5 13
1 5
3 2

arbori_xor.out

8
3

Explicație

Pentru prima cerinţă avem 4 ^ 1 ^ 13 = 8, iar pentru a doua 4 ^ 7 = 3.