Background

A国遭到了敌军入侵！ A国与S国曾经发生过一个小冲突： A国的国王syt认识了一个网友，是S国的国王lxy，二人交谈甚欢，一见如故。lxy是个男生，但是syt却始终认为lxy是个萌妹子，在得知真相后，syt狡辩说他称所有人都是姐姐，但是lxy并不买账，他将自己的军队倾巢出动，想攻下A国并活捉syt（？？），他决定先派出一些侦察兵到A国侦察，但是lxy得知了这件事，在各地安插了反侦察人员，但是lxy心生一计，他不准备逮捕这些侦察人员，反而要记录他们的轨迹，以便传递假情报给他们，但是lxy的反侦察人员很懒，他们只在某一时刻去工作，打完卡后就去划水了，为了统计每个人的出勤率，lxy希望你能帮助他记录每个反侦察人员能侦察到几个S国的侦查人员。

Description

A国总共有$n$个城市，$n-1$条道路，并且每座城市都直接或间接相连。 S国总共派出$m$个侦查人员，他们在一条简单路径上移动，到达终点后就返回S国。 每个反侦察人员都有一个侦察时间$w_i$，代表他将在第$w_i$天工作。 每个侦察人员都有两个参数$s_i,t_i$，表示他将从$s_i$出发，$t_i$返回。注意侦察人员在起点、终点也会停留。并令起点的时刻为0天，同时在城市间移动所需要的时间均为1天。

Input

第一行两个整数$n,m$ 接下来$n-1$行有两个整数$a_i,b_i$,表示城市$a_i$和$b_i$间有一条道路 接下来一行$n$个整数，第$i$个整数为$w_i$ 最后$m$行每行两个整数$s_i,t_i$ 意义见Description。

Output

输出一行$n$个整数，第$i$个数表示在城市$i$的反侦查人员能够侦察到的人的数量。

Samples

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

2 0 0 1 1 1 

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

1 2 1 0 1 

Limitation

对于$100$的数据：$1\le s_i,t_i\le n,0\le w_i\le n$
每个测试点的数据规模及特点如下表所示