Urządzenie „幻光留影” (Photo) można przedstawić jako drzewo o $n$ wierzchołkach, gdzie każdy wierzchołek reprezentuje punkt obrazu, a wierzchołek $i$ ($1 \le i \le n$) ma kolor filtra $c_i$. Istnieje $n-1$ wiązek światła łączących wierzchołki, ponumerowanych od $1$ do $n-1$.

W trakcie badania właściwości urządzenia zarejestrowano dane z $m$ testów efektów dynamicznych. Dla każdego testu określasz przedział numerów wiązek $[l, r]$. Zakładając, że aktywowane są tylko wiązki o numerach z tego przedziału (pozostałe wiązki są rozłączone), pierwotna sieć rozpada się na kilka niezależnych składowych spójnych.

Wewnątrz każdej składowej spójnej zachodzi interferencja optyczna między wierzchołkami o tym samym kolorze filtra: jeśli dany kolor filtra występuje w składowej parzystą liczbę razy, jego światło znosi się i staje się niewidoczne; jeśli występuje nieparzystą liczbę razy, skupia się w wyraźnie widoczny kolor.

Aby głębiej przeanalizować te zmiany, dla każdego testu należy obliczyć sumę liczby widocznych kolorów filtrów (czyli takich, które występują nieparzystą liczbę razy) we wszystkich składowych spójnych.

Wejście

Pierwsza linia wejścia zawiera dwie dodatnie liczby całkowite $n, m$ ($1 \le n \le 3 \times 10^5$, $1 \le m \le 10^6$), oznaczające odpowiednio liczbę wierzchołków obrazu oraz liczbę testów.

Druga linia zawiera $n$ dodatnich liczb całkowitych $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), oznaczających kolory filtrów każdego z wierzchołków.

Następnie $n-1$ linii, z których $i$-ta ($1 \le i \le n-1$) zawiera dwie dodatnie liczby całkowite $u_i, v_i$ ($1 \le u_i, v_i \le n$), oznaczające dwa wierzchołki połączone wiązką o numerze $i$.

Kolejne $m$ linii zawiera po dwie dodatnie liczby całkowite $l, r$ ($1 \le l \le r \le n-1$), oznaczające przedział numerów wiązek dla danego testu.

Wyjście

Wypisz $m$ linii, każda zawierająca nieujemną liczbę całkowitą, oznaczającą sumę liczby widocznych kolorów filtrów we wszystkich niezależnych składowych spójnych dla każdego testu.

Przykład

Wejście 1

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

Wyjście 1

10
12
12
12
6
8
10
4
8
12
4
10
12