测试数据来自 system/1930

描述

木姑娘来上海玩，这真是我的荣幸。

我带她去了很多狠多地方，等到夜幕降临，我们一起来到了东方明珠下。

适逢音乐节，东方明珠下被人装点了一株音乐树。木姑娘穿着一身白裙子，站在音乐树下，楚楚动人。

音乐树的藤蔓与树叉可以被抽象地看作是一个树结构。每一个结点 x 都对应了一个音符，它的音高为 Hx。

木姑娘每一次会选择两个结点 s 和 t，得到树上的一条路径。我会按照她的指示，去弹奏路径上的音符，弹奏出来的音符会挂在天边。

这样的音乐或许是枯燥的。从 s 出发，到 t 结束。当到达结点 x 的时候，所有音高大于 Sx 的音符会消失，在这之后，会出现一个音高为 Hx 的音符。同样音高的音符可以有很多个。

有的时候，木姑娘还会稍微修正某个结点上的 Sx，为了让这个有音乐的夜晚更加美好。

格式

输入格式

第一行有两个整数N，M ，表示节点数与事件数。
接下来的N-1行，每行两个整数ui，vi ，描述一条连接节点ui与节点vi的边。
接下来的一行，N个整数Hi 。
接下来的一行，N个整数Si 。
接下来的M行，每行表示一个事件，它们的形式如下：
M x val : 将Sx修改为val
Q x y : 如果木姑娘选中了路径x->y，那么在音乐结束（也就是到达终点y的时候）还剩下多少音符。

输出格式

对于每组询问，输出一行答案。

样例1

样例输入1

7 3
1 2
2 3
3 4
4 5
5 6
6 7
3 2 4 5 7 1 2
1 6 3 2 3 4 2
Q 1 7
M 6 1
Q 1 7

样例输出1

3
2

限制

存在15％的数据，1<=N,M<=5000 ，保证给出的边形成一条链，数据中不含M操作。
存在20％的数据，保证给出的边形成一条链，数据中不含M操作。
存在10％的数据，保证给出的边形成一条链。
存在25％的数据，数据中不含M操作。
存在30％的数据，无追加限制。
对于100％的数据，1<=N<=40000，1<=M<=60000，1<=Hi,Si,val<=50000，1<=x,y,ui,vi<=N