Cô bò Bessie đang trồng cỏ trên một đường thẳng. Nàng bò nhà ta có \(N\) \((1 \leq N \leq 2 * 10^5)\) giống cỏ khác nhau, giống cỏ \(i\) sẽ được trồng trên đoạn \([l_i, r_i]\) \((0 < l_i < r_i \leq 10^9)\).

Thêm nữa, giống cỏ \(i\) còn tăng trưởng tốt hơn khi có một số giống cỏ \(j\) \((j \ne i)\) nào đó mà giống cỏ \(i\) và \(j\) cùng được trồng trên \(1\) đoạn giao nhau với độ dài tối thiểu là \(k_i\) \((0 < k_i \leq r_i - l_i)\). Bessie muốn phỏng đoán sự tăng trưởng của các giống này, vì thế nên với mỗi giống cỏ \(i\), cô nàng muốn biết có bao nhiêu giống cỏ \(j \ne i\) mà giống cỏ \(j\) và \(i\) cùng được trồng trên \(1\) đoạn giao nhau với độ dài không bé hơn \(k_i\) nhé!

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(3\) số nguyên dương \(l_i\), \(r_i\) và \(k_i\).

Output

• Gồm \(N\) dòng, trong đó dòng thứ \(i\) là đáp án của giống cỏ \(i\).

Scoring

• Subtask \(1\): \(N \leq 5000\).
• Subtask \(2\): \(k_i\) giống nhau \(\forall i \in [1, N]\).
• Subtask \(3\): Không có ràng buộc gì thêm.

Example

2
3 6 3
4 7 2

0
1

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

3
3
2
2

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

0
3
1
3
3