黄YY是一个清明梦超能力者，同时也是一个记忆大师。他能够轻松控制自己在梦中的一切，在醒来之后还能清晰的记得梦中所有的细节，这让他的朋友们都十分羡慕。
又是一个晚上，黄YY又到了自己的梦中，并且随手造出了一棵有n个点的树，树上每个点有一个初始颜色0。为了让这棵树不那么单调，黄YY拿起了画笔在上面尽情上色。每一次上色可以用u,
v, c来描述，代表黄YY把u, v这条路径上的点都染色成了c。
正当黄YY开心的完成了m次染色，准备在早上醒来之时向朋友们炫耀。但现实中的黄YY由于过于兴奋滚到了床下，撞到了脑袋，在剧痛中醒来。由于脑部受到了严重创伤，黄YY对刚才梦境中发生的一切发生了严重的信息丢失。
但英俊潇洒的黄YY当然不希望自己的窘态被朋友们发现。为了证明自己还是那个清明梦超能力者，他希望告诉朋友们自己上色后每个节点的颜色。同时为了更进一步证明他还是个记忆大师，他希望干脆直接说出每个点在倒数第k次染色时的颜色。
当然，现在的黄YY已经成了弱智了，作为黄YY最亲密的朋友，你快来帮帮黄YY吧！

第一行三个整数n, m, k，代表树的点数，黄YY染色的次数，以及最后求颜色时，倒数的次数（1 ≤ n, m, k ≤ 100000）。
接下来n - 1行，每行u, v代表u, v两点之间有一条边。这里保证1 ≤ u, v
≤ n，且无重边与自环，是一棵标准的树。
接下来m行，每一行三个数字u, v, c代表黄YY在第这次用c颜色的画笔从u涂到了v。

一行$n$个数字，输出每个点倒数第$k$次染色时的颜色。如果本身不足$k$次，输出0。

3 3 2
1 2
2 3
1 2 1
2 3 2
1 3 3

1 2 2

对于点1在第一次和第三次染色的时候分别被染色为1, 3，倒数第二次的颜色就是1。
对于点2在第一、二、三次染色的时候分别被染色为1, 2, 3，倒数第二次的颜色就是2。
对于点3在第二次和第三次染色的时候分别被染色为2, 3，倒数第二次的颜色就是2。