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\)