背景

JPY有一颗知识树
随着JPY的学习，知识的掌握发生变化
SBW想知道JPY知识掌握情况，于是向你求助
并答应告诉你JPY的笔记本型号

描述

给出一颗N个点的树
点有点权
M个操作
每个操作给出两个值d,x
若d==0 表示询问点x的权
否则 表示所有与x距离<=d的点权值+=d

输入

第一行两个正整数N,M
第二行N个正整数
其中第i个数为点i的初始点权\(v_i\)
接下来N-1行
每行两个数a,b表示a,b之间有一条长度为1的边
接下来M行
每行两个自然数d,x

输出

对每个询问，一行一个整数为询问答案

样例

输入

6 5
1 2 3 4 5 6
1 2
2 3
2 4
3 5
2 6
1 2
0 2
0 3
2 2
0 5

输出

3
4
7

范围

50% N<=3000 M<=3000
60% N<=5000 M<=5000
80% N<=30000 M<=50000
90% N<=100000 M<=100000
100% N<=300000 M<=300000 \(v_i\)<=10000 0<=d<=200 1<=x<=N

限制

3s
256M