题目描述

小海棠得到了顶点个数为n的树，树的编号从1到n，每个节点都有一个命令编号(所有节点的命令编号初始为0)。 小海棠指定1为树的根，她每次将向某个节点发送命令X，节点在接到命令后将本节点的命令编号更新为x，并向自己所有子节点传播命令x，小海棠想直到在她执行完所有命令后每个节点的命令编号是多少。

输入描述

多组样例，第一行包含一个整数T表示样例组数。 每组样例第一行包含两个整数n,k 分别表示节点个数和指令的条数。 第二行包含$n-1$个整数，第$i$个整数表示节点$(i+1)$的父亲节点为$a_i$。 接下来k行每行包含两个整数x,y，表示对x节点执行指令y。

输出描述

每组样例输出一行用空格分离的n个整数，表示所有命令执行完成后的命令编号

样例

输入1

2
3 2
1 2
1 1895
2 129
4 1
1 1 1
3 1

输出1

1895 129 129
0 0 1 0

提示

$T <= 20$, $n,k <= 100000$, $1<=x<=100000$