背景

sro VisJiao orz
VisJiao有一棵知识树

描述

给出一棵N个点的树
点有点权，边有长度
M个操作

输入

第一行两个数N,M
第二行N个数，为各点点权\(V_i\)
接下来N-1行
每行三个数a,b,l
表点a与点b之间有一条长为l的边
接下来M行
每行一个操作
Q P L 表示询问到P距离<=L的点的点权和
A P L V 表示所有到P距离<=L的点的点权+=V

输出

对于每个询问
输出点权和

样例

输入

5 5
6 2 5 1 3
1 2 10
2 5 20
1 4 50
1 3 20
Q 1 15
A 1 30 1
Q 1 40
A 2 20 2
Q 4 75

输出

8
20
21

范围

80% N,M<=5000
100% N,M<=10000 1<=a,b<=N 1<=l<=1000 \(|V_i|\),|V|<=1000

限制

2s
512M