Фоне

Чтобы оставить уникальное воспоминание о десятилетии, Сяо Т и Сяо С установили в главном зале крупную интерактивную художественную инсталляцию «Фото».

Эта инсталляция состоит из множества подвешенных узлов изображения, соединенных световыми лучами в форме дерева, причем каждому узлу присвоен световой фильтр определенного цвета. Подойдя к консоли управления, вы обнаружили, что можете свободно взаимодействовать с ней: каждый раз, когда вы настраиваете параметры на консоли, система временно активирует только световые лучи с номерами в заданном диапазоне, из-за чего исходная целостная сеть распадается на несколько независимых связных компонент.

Интересно, что между узлами с фильтрами одного цвета в пределах одной связной компоненты происходит оптическая интерференция: когда фильтр определенного цвета встречается в этой компоненте четное число раз, его свет взаимно уничтожается и становится невидимым; когда же он встречается нечетное число раз, он собирается в четко видимый цвет.

Процесс разрушения и рекомбинации света и тени весьма увлекателен, и вы проявили глубокий интерес к скрытым структурным изменениям: при каждой такой локальной активации, сколько всего различных видимых фильтров содержится во всех образовавшихся связных компонентах?

Описание

Инсталляцию «Фото» можно представить как дерево с $n$ узлами, где каждый узел представляет собой узел изображения, а цвет фильтра узла $i$ ($1 \le i \le n$) равен $c_i$. Всего имеется $n-1$ световой луч, соединяющий узлы, пронумерованные от $1$ до $n-1$.

В процессе исследования закономерностей вы записали данные $m$ тестов динамических эффектов. Для каждого теста вы задаете диапазон номеров лучей $[l, r]$. Предположим, что в этот момент активируются только лучи, номера которых попадают в этот диапазон (остальные лучи, номера которых не входят в этот диапазон, отключаются), в результате чего исходная связная сеть распадается на несколько независимых связных компонент.

Для более глубокого анализа изменений вам необходимо для каждого теста вычислить: сумму количеств различных видимых фильтров (то есть цветов фильтров, которые встречаются нечетное число раз) в каждой из связных компонент.

Входные данные

Первая строка ввода содержит два целых положительных числа $n, m$ ($1 \le n \le 3 \times 10^5, 1 \le m \le 10^6$), обозначающие количество узлов изображения и количество тестов соответственно.

Вторая строка ввода содержит $n$ целых положительных чисел $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), обозначающих цвет фильтра каждого узла изображения.

Далее следуют $n-1$ строк, $i$-я строка ($1 \le i \le n-1$) содержит два целых положительных числа $u_i, v_i$ ($1 \le u_i, v_i \le n$), обозначающих два узла, соединенных лучом с номером $i$.

Далее следуют $m$ строк, каждая из которых содержит два целых положительных числа $l, r$ ($1 \le l \le r \le n-1$), обозначающих диапазон номеров лучей для одного теста.

Выходные данные

Выведите $m$ строк, в каждой из которых содержится одно неотрицательное целое число, последовательно обозначающее сумму количеств различных видимых фильтров в каждой из независимых связных компонент для каждого теста.

Примеры

Входные данные 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

Выходные данные 1

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