Batyr 最近开始研究树。但他并不是一位树木学家，所以他研究的是具有 $n$ 个顶点和 $n-1$ 条边的连通图的性质。

假设 $T$ 是一个具有 $n$ 个带标号顶点的无向树。Batyr 定义了一个函数 $f(S)$：包含 $S$ 中所有顶点的 $T$ 的连通子图的最小规模（节点数），其中 $S$ 是 $T$ 的任意顶点子集。换句话说，想象一下在 $T$ 中删除尽可能多的顶点，使得 $S$ 中的所有顶点仍然保持连通。所得树的大小即为 $f(S)$。

作为一名高级研究员，Batyr 对这些琐事并不满足。他已经选定了一棵树 $T$ 并将其画在白板上。然后，他在每个顶点上都贴了一个带有 $1$ 到 $n$ 之间唯一编号的小磁铁。顶点的索引和贴在上面的磁铁编号可能不同：编号为 $p_i$ 的磁铁贴在顶点 $i$ 上。因此，磁铁上的数字构成了一个排列 $p = [p_1, p_2, \dots, p_n]$。

Batyr 考虑子集 $S_{l,r} = \{i : l \le p_i \le r\}$，这些子集由贴在上面的磁铁编号在 $l$ 到 $r$ 范围内的顶点组成（$1 \le l \le r \le n$）。与此相关，他感兴趣的是函数 $g(p)$ —— 即所有 $l$ 和 $r$ 对的 $f(S_{l,r})$ 之和。

但 Batyr 研究的关键问题是分析 $g(p)$ 在排列 $p$ 的微小修改下的行为。他提出了 $q$ 个修改查询：第 $j$ 个查询表示交换贴在第 $c_j$ 条边端点上的磁铁。修改是复合的：在应用第 $j$ 个修改时，会考虑前 $j-1$ 次修改的影响。

作为 Batyr 的研究助理，你再次被分配了这些枯燥的工作。你需要计算在排列 $p$ 修改前以及每次修改后 $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)$ 的值 —— 即所有 $l$ 和 $r$ 对的 $f(S_{l,r})$ 之和。

然后对于每个查询，在第 $i$ 行打印交换顶点 $a_{c_i}$ 和 $b_{c_i}$ 上的磁铁后 $g(p)$ 的值。

子任务

本题包含 8 个子任务，满足以下要求：

1. 本说明中的测试用例。分值为 0。
2. $n \le 1000, q = 0$。保证对于所有 $1 \le i < n$，$a_i = i, b_i = i + 1$。分值为 9。
3. $n \le 10^5, q = 0$。保证对于所有 $1 \le i < n$，$a_i = 1, b_i = i + 1$。分值为 10。
4. $n \le 10^5, q = 0$。保证对于所有 $1 \le i < n$，$a_i = i, b_i = i + 1$。分值为 11。
5. $n \le 1000, q = 0$。分值为 16。
6. $n, q \le 10^5$。保证对于所有 $1 \le i < n$，$a_i = i, b_i = i + 1$。分值为 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})$ 是包含 $S_{1,1}$ 中所有顶点的连通子图的最小规模 $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$。