Description

JMT有一棵树。其中 $1$ 号节点为根节点。
定义在这颗树上删除一个点（被删除的点不为根节点）为将这个点的所有儿子节点直接连到这个点的父亲节点，并将这个点和它所相连的所有边删除。树上的每一个点有一个点权，表示删除它这一个点的代价。
定义一个节点的深度为它父亲节点的深度加 $1$ , 根节点的深度为 $1$ 。
一共有两种操作，分别形如：
$C$ $x$ $y$ 表示将编号为 $x$ 的点的点权修改为 $y$ 。
$Q$ $x$ $y$ 询问将编号为 $x$ 的点的深度变为 $y$ 所需要花的删点代价和最小是多少（如果深度永远不可能变为 $y$ ，输出 $-1$ ）。**注意:每一个 $Q$ 操作是独立的。也就是说，在删完之后会还原。**

Format

Input

第一行有两个整数 $n$ ，$q$ 表示树的节点数目和询问次数。
接下来 $n - 1$ 行，每行两个整数，表示树上一条边。
接下来一行有 $n - 1$ 个整数，第 $i$ 个表示第 $i + 1$ 号节点的初始权值。
接下来 $q$ 行，表示询问。询问格式如题。

Output

第一行有两个整数 $n$ ，$q$ 表示树的节点数目和询问次数。
接下来 $n - 1$ 行，每行两个整数，表示树上一条边。
接下来一行有 $n - 1$ 个整数，第 $i$ 个表示第 $i + 1$ 号节点的初始权值。
接下来 $q$ 行，表示询问。询问格式如题。

Sample 1

Input

6 4
1 2
2 4
2 5
5 6
1 3
2 3 4 5 6
Q 4 2
C 2 1
Q 4 2
Q 5 4

Output

2
1
-1

Limitation

对于 $15\%$ 的数据：$1 \leq n \leq 10^3 ,1 \leq q \leq 10^4$
对于另 $10\%$ 的数据：保证树为一条链
对于另 $20\%$ 的数据： $C$ 操作次数不超过 $100$
对于另 $5\%$ 的数据： 树形态随机生成
对于 $100\%$ 的数据：
$1 \leq n \leq 10^4$
$1 \leq 点权 \leq 10^3$
$1 \leq q \leq 10^5$