Contexto

Para dejar un recuerdo único del décimo aniversario, el pequeño T y el pequeño S instalaron una gran instalación de arte interactivo llamada "Photo" en el recinto principal.

Este dispositivo está compuesto por muchos nodos de imagen suspendidos, conectados por haces de luz para formar una estructura de árbol, y cada nodo tiene configurado un filtro de luz y sombra de un color diferente. Al llegar a la consola, descubres que puedes interactuar libremente: cada vez que ajustas los parámetros en la consola, el sistema activa temporalmente solo los haces de luz dentro de un rango de numeración específico, lo que hace que la red de imágenes, originalmente completa, se divida en varios subcomponentes conectados independientes.

Lo ingenioso es que, dentro del mismo subcomponente conectado, los nodos con el mismo tipo de filtro experimentarán interferencia óptica: cuando un filtro de cierto color aparece un número par de veces en ese subcomponente, su luz se cancela y se vuelve invisible; mientras que cuando aparece un número impar de veces, converge en un color claramente visible.

La fragmentación y recombinación de luces y sombras es fascinante, y te has interesado profundamente en los cambios estructurales ocultos: bajo cada activación local de este tipo, ¿cuántos tipos de filtros visibles contiene cada uno de los subcomponentes conectados resultantes?

Descripción

El dispositivo "Photo" puede abstraerse como un árbol que contiene $n$ nodos, donde cada nodo representa un nodo de imagen y el nodo $i$ ($1 \le i \le n$) tiene un color de filtro $c_i$. Hay $n-1$ haces de luz que conectan los nodos, numerados secuencialmente del $1$ al $n-1$.

Durante tu exploración, registraste datos de $m$ pruebas de efectos dinámicos. Para cada prueba, especificas un intervalo de numeración de haces de luz $[l, r]$. Supongamos que en ese momento solo se activan los haces de luz cuyas numeraciones caen dentro de dicho intervalo (desconectando los demás haces de luz fuera de este intervalo), lo que provoca que toda la red, originalmente conectada, se divida en varios componentes conexos independientes.

Para analizar más a fondo los cambios, necesitas calcular para cada prueba: la suma total de la cantidad de tipos de filtros visibles (es decir, colores de filtro que aparecen un número impar de veces) contenidos en cada componente conexo.

Entrada

La primera línea contiene dos enteros positivos $n, m$ ($1 \le n \le 3 \times 10^5$, $1 \le m \le 10^6$), que representan la cantidad de nodos de imagen y la cantidad de pruebas, respectivamente.

La segunda línea contiene $n$ enteros positivos $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), que representan el color del filtro de cada nodo de imagen.

Las siguientes $n-1$ líneas, la $i$-ésima línea ($1 \le i \le n-1$) contiene dos enteros positivos $u_i, v_i$ ($1 \le u_i, v_i \le n$), que representan los dos nodos conectados por el haz de luz numerado como $i$.

Las siguientes $m$ líneas, cada una contiene dos enteros positivos $l, r$ ($1 \le l \le r \le n-1$), que representan el intervalo de numeración de los haces de luz para una prueba.

Salida

Imprime $m$ líneas, cada una con un entero no negativo, que representen la suma total de la cantidad de tipos de filtros visibles contenidos en cada componente conexo independiente para cada prueba, respectivamente.

Ejemplos

Entrada 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

Salida 1

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