Zapytania o drzewo#236
Dostajesz połączony graf z wierzchołkami i n-1 krawędziami – innymi słowy, jest to drzewo. Wierzchołek jest korzeniem drzewa. Na wierzchołku jest zapisana liczba całkowita a_v. Koszt drzewa definiujemy jako operacja bitowa XOR wszystkich jego wartości. Dostajesz zapytań, zawierających dwie liczby całkowite i . Każde zapytanie wykonuje a_u = a_u \oplus x dla wszystkich należących do poddrzewa wierzchołka , a oznacza operację XOR. Jak wiadomo, ten problem może być łatwo rozwiązany przez naszych uczestników, ale gdyby wszystko było takie łatwe, ten problem nie pojawiłby się na tej olimpiadzie. Wiesz, że niektóre zapytania zostały zmienione przez złośliwego Antona. Zatem prosisz o znalezienie sumy kosztów modulo , wszystkich 2^q drzew, które można uzyskać przez zastosowanie niektórych (być może żadnych) zapytań na drzewie.
Pierwsza linia wejścia zawiera dwie liczby całkowite (1 \le n \le 2 \cdot 10^5) i (1 \le q \le 2 \cdot 10^5) — liczba wierzchołków w drzewie i liczba zapytań odpowiednio.
Druga linia wejścia zawiera liczb całkowitych a_i (0 \le a_i < 2^{60}) — wartości zapisane na wierzchołkach drzewa.
Następne n-1 linii zawierają po dwie liczby całkowite i każda — krawędzie danego drzewa.
Następne linii zawierają po dwie liczby całkowite (1 \le v \le n) i (0 \le x < 2^{60}) każda — opis zapytań.
Wypisz jedną liczbę całkowitą w pierwszej linii — odpowiedź na problem.
Przykład 1
( punktów): q \le 2;
( punktów): q \le 10;
( punktów): q \le 20;
( punktów): a_i, x < 2;
( punktów): a_i, x < 1024;
( punktów): a_i, x < 2^{18};
( punktów): brak dodatkowych ograniczeń.