## USACO 2024 US Open Contest, Gold

## Problem 2. Grass Segments

Contest has ended.

**Log in to allow submissions in analysis mode**

Bessie is planting some grass on the positive real line. She has $N$ ($2\le N\le 2\cdot 10^5$) different cultivars of grass, and will plant the $i$th cultivar on the interval $[\ell_i, r_i]$ ($0 < \ell_i < r_i \leq 10^9$).

In addition, cultivar $i$ grows better when there is some cultivar $j$ ($j\neq i$) such that cultivar $j$ and cultivar $i$ overlap with length at least $k_i$ ($0 < k_i \leq r_i - \ell_i$). Bessie wants to evaluate all of her cultivars. For each $i$, compute the number of $j\neq i$ such that $j$ and $i$ overlap with length at least $k_i$.

#### INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$.The next $N$ lines each contain three space-separated integers $\ell_i$, $r_i$, and $k_i$.

#### OUTPUT FORMAT (print output to the terminal / stdout):

The answers for all cultivars on separate lines.#### SAMPLE INPUT:

2 3 6 3 4 7 2

#### SAMPLE OUTPUT:

0 1

The overlaps of the cultivars is $[4,6]$, which has length $2$, which is at least $2$ but not at least $3$.

#### SAMPLE INPUT:

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

#### SAMPLE OUTPUT:

3 3 2 2

#### SAMPLE INPUT:

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

#### SAMPLE OUTPUT:

0 3 1 3 3

#### SCORING:

- Input 4-5: $N \leq 5000$
- Inputs 6-11: $k$ is the same for all intervals
- Inputs 12-20: No additional constraints.

In addition, for Inputs 5, 7, ..., 19, $r_i \leq 2N$ for all $i$.

Problem credits: Benjamin Qi