Minimum Passports for Asia Travel

Gospodin Malnar plans to travel in Asia visiting \(N\) cities. The cities are connected by \(N-1\) bidirectional highways forming a tree, and the travel starts at city 1. There are \(M\) different types of passports available, numbered from 1 to \(M\). Each highway \(i\) connects cities \(a_i\) and \(b_i\) and requires you to purchase all passports with types in the interval \([l_i, r_i]\). For any destination city \(i\) (\(2 \le i \le N\)), you are to compute the minimum number of passports needed along the unique path from city 1 to city \(i\). The required number is equal to the size of the union of the intervals on that path. In other words, if the union of intervals is \(\bigcup [l, r]\) then the answer is \(\sum (r - l + 1)\).

inputFormat

The first line contains two integers \(N\) and \(M\) -- the number of cities and the number of passport types, respectively. Each of the next \(N-1\) lines contains four integers \(a_i\), \(b_i\), \(l_i\) and \(r_i\), describing a highway between cities \(a_i\) and \(b_i\) that requires all passport types in the range \([l_i, r_i]\) (inclusive) to traverse.

outputFormat

For each city \(i\) from \(2\) to \(N\), print a single integer on a new line representing the minimum number of passports required to travel from city 1 to city \(i\).

sample

3 10
1 2 1 3
1 3 2 4

3
3