Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Adam Young

By Iftekhar_Hakim · Limits 1s, 512 MB

“It's hard to say that I'd rather stay awake when I'm asleep
'Cause everything is never as it seems (when I fall asleep)”

Adam Young finally woke up. He discovered himself in Number-land. Number-land can be described as a rooted tree of nn junctions, where junction 11 is the root. Each junction ii is connected with its parent junction pip_i by a road and an integer viv_i is written on that road.

Adam will start walking from junction xx with his board. Initially, his board has 00 written on it. In every second, Adam can walk from his current junction to its parent junction by the road connecting them, or he can finish walking in his current junction. Of course, he cannot walk upward from the root junction. Whenever he crosses a road, he immediately adds the number written on that road to his board’s number.

Adam wants to maximize the final number written on his board after he finished his walking. But he will be sad if it is not divisible by his favorite number KK. Help Adam finding the maximum number he can get on his board without being sad.

You have to find it for all xx (1xn)(1\le x \le n) independently, where xx is his starting junction.

Help your friend Adam Young, otherwise he will sleep again and stop making best songs.

Input

First line of input will have number of junctions nn (1n105)(1\le n \le 10^5) and Adam’s favorite number KK (1K105)(1\le K \le 10^5).

Second line will have n1n-1 integers describing pip_i (1pin)(1\le p_i \le n) for 2in2\le i \le n respectively.

Third line will have n1n-1 integers describing viv_i (109vi109)(-10^9 \le v_i \le 10^9) for 2in2\le i \le n respectively.

Output

Output a single line consisting of nn integers. ii-th integer will be the maximum number Adam can get on his board without being sad, if he starts walking from junction ii.

Sample

InputOutput
7 2
1 1 2 4 3 3
4 -4 -2 2 2 1
0 4 0 2 4 2 0

This is the tree of sample input and K=2K=2.

For junction 11, Adam cannot move anywhere.

For junction 22, 44 and 55, he will go upto junction 11.

For junction 33, it is optimal to move nowhere.

For junction 66, he will move upto junction 33.

For junction 77, it is optimal to move nowhere. Note that, he cannot finish at junction 33 starting from 77, as his board’s number will not be divisible by KK.

Discussion

Statistics


92% Solution Ratio

alifcsejuEarliest, 2M ago

shefinFastest, 0.0s

Sunset_Lightest, 24 MB

Azizur_RahmanShortest, 890B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.