题目描述

Bessie 正在数轴的正半轴上种一些草。她有 $N$（$2\le N\le 2\cdot 10^5$）个不同的栽培品种，并将把第 $i$ 个品种种植在区间 $[l_i,r_i]$（$0<l_i<r_i\le 10^9$）内。

此外，品种 $i$ 会在存在某个品种 $j$（$j\neq i$）使得品种 $j$ 与品种 $i$ 重叠至少 $k_i$（$0<k_i\le r_i-l_i$）长度时生长得更好。Bessie 想要评估她所有的品种。对于每一个 $i$，计算 $j\neq i$ 的数量，使得 $j$ 与 $i$ 重叠至少 $k_i$ 长度。

输入格式

输入的第一行包含 $N$。

以下 $N$ 行每行包含三个空格分隔的整数 $l_i$，$r_i$ 和 $k_i$。

输出格式

输出所有品种的答案，每种一行。

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

提示

样例解释 1

两品种的重叠部分为 $[4,6]$，长度为 $2$，不小于 $2$ 但并非不小于 $3$。

测试点性质

• 测试点 $4-5$：$N\le 5000$。
• 测试点 $6-11$：$k$ 对于所有的区间均相同。
• 测试点 $12-20$：没有额外限制。

此外，对于测试点 $5$，$7$，……，$19$，对于所有 $i$ 有 $r_i\le 2N$。