EIU Programming Practices and Exams

King of Planet NP wants to plant more trees to increase the beauty of his planet. He asked the local authorities to report the number of trees to be planted. Each locality will synthesize from the reports of subordinate units (eg district level will synthesize from commune level). The kingdom consists of N administrative units numbered from 0 to N-1. The kingdom is considered the largest administrative unit. Given the number of trees of the smallest-level units and the kingdom's administrative map, determine the number of trees each will grow.

Input

The first line contains two integers n, m (0 ≤ m <n ≤ 10⁵) representing the number of administrative units of the kingdom and the code of the administrative units indicating the kingdom.

Each line in the n - 1 next line has two integers a and b representing b is the direct administrative unit of a.

Each of the remaining lines contains two integers u and q representing the unit u planting q trees. The data ensures that u is the smallest administrative unit and no other administrative units are attached to u and all the smallest administrative units report the number of trees they grow.

Output

Consists of n lines, each containing the administrative unit number and the number of trees to be planted in that unit. The results are sorted by increasing number of administrative units.

Example

Input:
6 1
1 0
0 2
0 5
1 3
3 4
2 10
4 50
5 10

Output:
0 20
1 70
2 10
3 50
4 50
5 10