该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

半仙有一颗苹果树，现在要对半仙要对他施法，施法完后半仙很好奇每个结点上苹果个数。

描述

给定一棵有 $n$ 个节点的树，原本树上没有苹果，现在有 $q$ 次修改操作：让所有满足距离给定节点偶数的点苹果加若干个（包括给定节点）。

树和距离：参见百度

输入格式

第一行有两个正整数 $n$ 和 $q$ ，分别表示结点数和操作数。

接下来 $n-1$ 行，有两个正整数 $x$ , $y$ ，表示点 $x$ 和点 $y$ 有一条边。

接下来 $q$ 行，有两个整数 $x$ , $y$ ，其中 $x$ 表示给定结点， $y$ 表示苹果增加个数。

输出格式

输出 $n$ 行，表示施法后每个结点苹果个数

4 2
1 3
2 3
2 4
1 2
4 1

2
2
1
1

数据范围

对于100%数据，$1\le n,q\le$ 100000，$1\le y\le$ 1000

特殊性质A：对于所有 $1\le i\le n-1$ 结点 $i$ 与结点$i+1$都有边

特殊性质B：满足结点 $1$ 与所有点都有边

提示

本题数据较大，请用快速的输入，输出方式。