Batyr se ha interesado recientemente por el estudio de árboles. Pero no es dendrólogo, así que en lugar de árboles reales, estudia las propiedades de grafos conexos con $n$ vértices y $n - 1$ aristas.

Supongamos que $T$ es un árbol no dirigido sobre $n$ vértices indexados. Batyr ha descrito una función $f(S)$: el tamaño mínimo (el número de nodos) de un subgrafo conexo de $T$ que contiene a todos los vértices en $S$, donde $S$ es un subconjunto arbitrario de vértices de $T$. En otras palabras, imagine borrar el número máximo de vértices en $T$ de tal manera que todos los vértices de $S$ permanezcan conectados. El tamaño del árbol resultante sería igual a $f(S)$.

Como investigador avanzado, Batyr no está satisfecho con tales trivialidades. Ya ha elegido un árbol $T$ y lo ha dibujado en una pizarra. Luego, ha colocado un pequeño imán con un número único del 1 al $n$ en cada vértice de la pizarra. El índice de un vértice y el número en el imán colocado en él pueden diferir: un imán con el número $p_i$ está colocado en el vértice $i$. Por lo tanto, los números en los imanes forman una permutación $p = [p_1, p_2, \dots, p_n]$.

Batyr considera los subconjuntos $S_{l,r} = \{i : l \le p_i \le r\}$ que consisten en vértices que tienen un número en el imán adjunto en el rango de $l$ a $r$ ($1 \le l \le r \le n$). Relacionado con esto, le interesa la función $g(p)$ — la suma de $f(S_{l,r})$ sobre todos los pares de $l$ y $r$.

Pero la pregunta clave de la investigación de Batyr es analizar el comportamiento de $g(p)$ bajo pequeñas modificaciones de la permutación $p$. Ha ideado $q$ consultas de modificación: la $j$-ésima consulta denota un intercambio de los imanes colocados en los vértices extremos de la $c_j$-ésima arista. Las modificaciones se acumulan: el efecto de las primeras $j - 1$ modificaciones se considera al aplicar la $j$-ésima.

Como asistente de investigación de Batyr, se le ha asignado una vez más solo el trabajo aburrido. Debe calcular los valores de $g(p)$ antes de cualquier modificación y después de cada una de ellas.

Entrada

La primera línea de la entrada contiene dos enteros $n$ y $q$ ($1 \le n, q \le 10^5$) — el número de vértices en el árbol y el número de consultas de modificación.

La segunda línea contiene $n$ enteros únicos $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) — los números en los imanes colocados en cada vértice.

Las siguientes $n-1$ líneas contienen dos enteros $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$) que describen la $i$-ésima arista del árbol.

Las últimas $q$ líneas describen las consultas. Cada línea contiene un entero $c_i$ ($1 \le c_i \le n - 1$), que denota un intercambio de los imanes colocados en los vértices $a_{c_i}$ y $b_{c_i}$.

Salida

La primera línea de la salida debe contener el valor de $g(p)$ — la suma de $f(S_{l,r})$ sobre todos los pares de $l$ y $r$.

Luego, para cada consulta, imprima en la $i$-ésima línea el valor de $g(p)$ después de intercambiar los imanes entre los vértices $a_{c_i}$ y $b_{c_i}$.

Subtareas

Este problema contiene 8 subtareas, que cumplen los siguientes requisitos:

1. Pruebas de este enunciado. Vale 0 puntos.
2. $n \le 1000, q = 0$. Se garantiza que $a_i = i, b_i = i + 1$ para todo $i$ ($1 \le i < n$). Vale 9 puntos.
3. $n \le 10^5, q = 0$. Se garantiza que $a_i = 1, b_i = i + 1$ para todo $i$ ($1 \le i < n$). Vale 10 puntos.
4. $n \le 10^5, q = 0$. Se garantiza que $a_i = i, b_i = i + 1$ para todo $i$ ($1 \le i < n$). Vale 11 puntos.
5. $n \le 1000, q = 0$. Vale 16 puntos.
6. $n, q \le 10^5$. Se garantiza que $a_i = i, b_i = i + 1$ para todo $i$ ($1 \le i < n$). Vale 16 puntos.
7. $n \le 10^5, q = 0$. Vale 20 puntos.
8. Restricciones originales del problema. Vale 18 puntos.

Ejemplos

Entrada 1

3 1
3 2 1
1 2
2 3
1

Salida 1

10
11

Nota

Consideremos el ejemplo anterior. Inicialmente $p = [3, 2, 1]$.

1. $S_{1,1} = \{3\}$; $f(S_{1,1}) = 1$
2. $S_{1,2} = \{2, 3\}$; $f(S_{1,2}) = 2$
3. $S_{1,3} = \{1, 2, 3\}$; $f(S_{1,3}) = 3$
4. $S_{2,2} = \{2\}$; $f(S_{2,2}) = 1$
5. $S_{2,3} = \{1, 2\}$; $f(S_{2,3}) = 2$
6. $S_{3,3} = \{1\}$; $f(S_{3,3}) = 1$

$g(p) = 1 + 2 + 3 + 1 + 2 + 1 = 10$.

Después de la primera modificación, los imanes en los extremos de la 1-ra arista se intercambian. Ahora $p$ es igual a $[2, 3, 1]$.

1. $S_{1,1} = \{3\}$; $f(S_{1,1}) = 1$
2. $S_{1,2} = \{1, 3\}$; $f(S_{1,2}) = 3$
3. $S_{1,3} = \{1, 2, 3\}$; $f(S_{1,3}) = 3$
4. $S_{2,2} = \{1\}$; $f(S_{2,2}) = 1$
5. $S_{2,3} = \{1, 2\}$; $f(S_{2,3}) = 2$
6. $S_{3,3} = \{2\}$; $f(S_{3,3}) = 1$

$g(p) = 1 + 3 + 3 + 1 + 2 + 1 = 11$.