Grass Planting Overlap

Bessie is planting grass along the positive half-axis. She has \(N\) different species, and the \(i\)th species will be planted over the interval \([l_i, r_i]\) with \(0 < l_i < r_i \le 10^9\). In addition, species \(i\) will grow better if there exists some other species \(j\) (\(j \neq i\)) such that the overlapping length of their intervals is at least \(k_i\) (where \(0 < k_i \le r_i - l_i\)). For each species \(i\), compute the number of species \(j \neq i\) that have an overlapping interval with species \(i\) of length at least \(k_i\).

The overlap length between two intervals \([l_i, r_i]\) and \([l_j, r_j]\) is defined as \[ \max\left(0, \min(r_i, r_j) - \max(l_i, l_j)\right). \]

Note: If for a species \(i\) we have \(r_i < l_i+k_i\), then no other species can overlap with it by at least \(k_i\) and the answer for that species is 0.

inputFormat

The first line contains a single integer \(N\) (\(2 \le N \le 2 \cdot 10^5\)), representing the number of species. The next \(N\) lines each contain three space-separated integers \(l_i\), \(r_i\), and \(k_i\) representing the left endpoint, right endpoint, and the required minimal overlap length for the \(i\)th species.

outputFormat

Output \(N\) lines. The \(i\)th line should contain a single integer denoting the number of species \(j\) (with \(j \neq i\)) whose interval overlaps with the \(i\)th species for at least a length of \(k_i\).

sample

3
1 5 2
2 4 1
3 6 2

2
2
1