Problem Description

Bessie is planting some grass on the positive half-axis of a number line. She has \( N \) (\( 2 \le N \le 2 \cdot 10^5 \)) different cultivation varieties and will plant the \( i \)-th variety within the interval \([l_i, r_i]\) (\( 0 < l_i < r_i \le 10^9 \)).

Additionally, variety \( i \) will grow better if there exists some variety \( j \) (\( j \neq i \)) such that variety \( j \) overlaps with variety \( i \) by at least \( k_i \) (\( 0 < k_i \le r_i - l_i \)) length. Bessie wants to evaluate all her varieties. For each \( i \), calculate the number of \( j \neq i \) such that \( j \) overlaps with \( i \) by at least \( k_i \) length.

Input Format

The first line of input contains \( N \).

The following \( N \) lines each contain three space-separated integers \( l_i \), \( r_i \), and \( k_i \).

Output Format

Output the answers for all varieties, one per line.

Sample Input and Output

Sample Input #1

2
3 6 3
4 7 2

Sample Output #1

0
1

Sample Input #2

4
3 6 1
2 5 1
4 10 1
1 4 1

Sample Output #2

3
3
2
2

Sample Input #3

5
8 10 2
4 9 2
3 7 4
5 7 1
2 7 1

Sample Output #3

0
3
1
3
3

Notes

Sample Explanation 1

The overlapping part of the two varieties is \([4, 6]\), with a length of 2, which is not less than 2 but not greater than 3.

Test Case Properties

• Test cases \( 4-5 \): \( N \le 5000 \).
• Test cases \( 6-11 \): \( k \) is the same for all intervals.
• Test cases \( 12-20 \): No additional restrictions.

Additionally, for test cases \( 5, 7, \ldots, 19 \), for all \( i \) there is \( r_i \le 2N \).

见题面 Input 部分

见题面 Output 部分