Батыр недавно увлекся изучением деревьев. Но он не дендролог, поэтому вместо настоящих деревьев он изучает свойства связных графов с $n$ вершинами и $n - 1$ ребром.

Пусть $T$ — неориентированное дерево на $n$ пронумерованных вершинах. Батыр описал функцию $f(S)$: минимальный размер (количество узлов) связного подграфа дерева $T$, который содержит все вершины из $S$, где $S$ — произвольное подмножество вершин $T$. Другими словами, представьте, что мы удаляем максимальное количество вершин в $T$ так, чтобы все вершины из $S$ оставались связными. Размер получившегося дерева будет равен $f(S)$.

Как продвинутый исследователь, Батыр не удовлетворяется такими тривиальностями. Он уже выбрал дерево $T$ и нарисовал его на доске. Затем он прикрепил к каждой вершине на доске маленький магнит с уникальным числом от $1$ до $n$. Индекс вершины и число на прикрепленном к ней магните могут различаться: магнит с числом $p_i$ прикреплен к вершине $i$. Таким образом, числа на магнитах образуют перестановку $p = [p_1, p_2, \dots, p_n]$.

Батыр рассматривает подмножества $S_{l,r} = \{i : l \le p_i \le r\}$, состоящие из вершин, у которых число на прикрепленном магните находится в диапазоне от $l$ до $r$ ($1 \le l \le r \le n$). В связи с этим его интересует функция $g(p)$ — сумма $f(S_{l,r})$ по всем парам $l$ и $r$.

Но ключевой вопрос исследования Батыра — проанализировать поведение $g(p)$ при небольших модификациях перестановки $p$. Он придумал $q$ модифицирующих запросов: $j$-й запрос означает обмен магнитов, прикрепленных к конечным вершинам $c_j$-го ребра. Модификации накапливаются: эффект первых $j - 1$ модификаций учитывается при применении $j$-й.

Как научному ассистенту Батыра, вам снова поручили только скучную работу. Вам нужно вычислить значения $g(p)$ до начала модификаций и после каждой из них.

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

Первая строка входных данных содержит два целых числа $n$ и $q$ ($1 \le n, q \le 10^5$) — количество вершин в дереве и количество модифицирующих запросов.

Вторая строка содержит $n$ уникальных целых чисел $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) — числа на магнитах, прикрепленных к каждой вершине.

Следующие $n-1$ строк содержат по два целых числа $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$), описывающих $i$-е ребро дерева.

Последние $q$ строк описывают запросы. Каждая строка содержит целое число $c_i$ ($1 \le c_i \le n - 1$), обозначающее обмен магнитов, прикрепленных к вершинам $a_{c_i}$ и $b_{c_i}$.

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

Первая строка вывода должна содержать значение $g(p)$ — сумму $f(S_{l,r})$ по всем парам $l$ и $r$.

Затем для каждого запроса выведите в $i$-й строке значение $g(p)$ после обмена магнитов между вершинами $a_{c_i}$ и $b_{c_i}$.

Подзадачи

Эта задача содержит 8 подзадач, соответствующих следующим требованиям:

1. Тесты из этого условия. 0 баллов.
2. $n \le 1000, q = 0$. Гарантируется, что $a_i = i, b_i = i + 1$ для всех $i$ ($1 \le i < n$). 9 баллов.
3. $n \le 10^5, q = 0$. Гарантируется, что $a_i = 1, b_i = i + 1$ для всех $i$ ($1 \le i < n$). 10 баллов.
4. $n \le 10^5, q = 0$. Гарантируется, что $a_i = i, b_i = i + 1$ для всех $i$ ($1 \le i < n$). 11 баллов.
5. $n \le 1000, q = 0$. 16 баллов.
6. $n, q \le 10^5$. Гарантируется, что $a_i = i, b_i = i + 1$ для всех $i$ ($1 \le i < n$). 16 баллов.
7. $n \le 10^5, q = 0$. 20 баллов.
8. Ограничения исходной задачи. 18 баллов.

Примеры

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

3 1
3 2 1
1 2
2 3
1

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

10
11

Примечание

Рассмотрим пример выше. Изначально $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$.

После первой модификации магниты на концах 1-го ребра меняются местами. Теперь $p$ равно $[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$.