Problem description

Łukasz dostał wymagającą pracę domową – ma opracować zadanie algorytmiczne. Oczywiście najtrudniejszą częścią tworzenia zadania jest wymyślenie zabawnej i wciągającej treści, dlatego Łukasz nawet nie pomyślał, żeby się za to zabrać. Na szczęście wymyślił wyjątkowo ciekawy problem, więc ma nadzieję, że nauczyciel przymknie oko na brak rozbudowanej treści.

Zadanie Łukasza brzmi następująco: mając dane N wierzchołkowe ważone drzewo (tj. nieskierowany graf spójny o N − 1 ważonych krawędziach) oraz pewną całkowitą liczbę nieujemną C, znajdź takie wierzchołki u oraz v, że XOR wartości C z wagami krawędzi na ścieżce między u a v jest maksymalny.

Niestety, Łukasz jest tragicznym koderem i poprosił Cię o napisanie wzorcówki do swojego zadania. Pomóż Łukaszowi! Napisz program, który wczyta wartość C oraz opis drzewa, po czym wyznaczy wartość maksymalnego XORa wartości C z wagami krawędzi na ścieżce między pewnymi (niekoniecznie różnymi) wierzchołkami drzewa.

Wejście

W pierwszym wejściu standardowego wejścia znajdują się dwie liczby całkowite N oraz C, oznaczające odpowiednio liczbę wierzchołków drzewa oraz wartość C potrzebną do liczenia XORa. W następnych N − 1 wierszach znajduje się opis krawędzi drzewa. i-ty z nich składa się z 3 liczb u_i, v_i, oraz w_i i oznacza, że między wierzchołkami u_i, v_i znajduje się krawędź o wadze w_i.

Wyjście

W pierwszym i ostatnim wierszu wejścia powinna znajdować się jedna nieujemna liczba całkowita X równa maksymalnemu XORowi wartości C z wagami krawędzi na ścieżce między pewnymi wierzchołkami drzewa.

Ograniczenia

1 ≤ N ≤ 200 000, 0 ≤ C, w_i ≤ 10¹⁸.

Przykład

7 3
1 2 1
2 3 3
5 6 6
4 1 6
5 4 10
7 4 2

15

5 0
3 2 8
4 2 10
2 1 12
5 2 14

14

10 14
1 2 7
1 4 8
5 1 5
3 1 11
7 4 6
6 4 13
9 7 3
8 3 6
5 10 8

14