暂无测试数据。

为了方便管理磁盘中的文件，你用文件夹管理它们，这些文件夹被编号为 $1,2,3,...,n$。

每个文件夹里有 $0$ 个或数个文件夹，除 $1$ 号文件夹之外，每个文件夹都在其它文件夹中，所有文件夹从 $1$ 到 $n$ 编号，编号为 $i$ 的文件夹里有一个文本文件Ti.txt，里面存储了一个整数 $w_i$。

你喜欢整理这些文件，你有时候会指定一个文件夹 $f$ 和一个参数 $x$，把这个文件夹里（包括其直接或间接子文件夹中的）所有 txt 文件的权值进行修改，每次修改的方式是以下所述之一：

1：给原来的数字加上 $x$。

2：把原先的数字用 $x$ 覆盖。

现在给出一开始每个 txt 文件中存储的数字，以及你所进行的操作，问最终每个 $w_i$ 的值是多少。

输入格式

第 $1$ 行给出两个整数，$n$，$m$ 表示事件数和操作次数。

接下来 $n$ 行，每行两个整数，第 $i$ 行的第一个数表示编号为 $i$ 的文件夹的上层文件夹的编号，第二个数表示 $w_i$，特殊地，用 $0$ 表示根目录（即 $1$ 号文件夹的上层目录）。

接下来 $m$ 行，每行三个整数 $type,f,x$ 表示一次操作，三个数分别代表操作的类型（$1$ 或 $2$）、所指定文件夹的编号 $f$，操作参数 $x$。

输出格式

$n$ 个空格隔开的数，按照 $i=1,2,3...n$ 的顺序给出 $w_i$。

数据范围

对于测试点 $1,2,3$，$n=m=1000$。

对于测试点 $4,5,6$，$n=m=500000$，除 $1$ 本身外，其它结点的上层文件夹都是 $1$ 号文件夹。

对于测试点 $7,8,9,10$，$n=m=500000$。

对于全部测试点，$0\le x\le 10$，$0\le w_i\le 1000$。

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

3 5 5 1 5