Page not loading? Try clicking here.
Placeholder

#8012
Subtask

잔디 심기 3s 1024MB

Problems

정올이는 N 종류의 잔디 종자를 심으려고 한다. i번째 종자는 구간 [ℓ_i, r_i]에 심을 예정이다.

또한, i번째 종자는 j (j ≠ i) 번째 종자와 적어도 k_i 만큼의 길이로 겹칠 때 더 잘 자란다.

정올이는 각 잔디 종자에 대해 최소 k_i 만큼 겹치는 다른 잔디 종자의 개수가 궁금해졌다.

이를 계산하는 프로그램을 작성하시오.


Input

첫 번째 줄에 정수 N이 주어진다. (2 ≤ N ≤ 200,000)

두 번째 줄부터 N줄에 걸쳐 세 정수 ℓ_i, r_i, k_i가 주어진다. (0 < ℓ_i < r_i ≤ 1,000,000,000, 0 < k_i ≤ r_i - ℓ_i)


Output

N줄에 걸쳐 i번째 줄에 i번째 잔디 종자가 최소 k_i 만큼 겹치는 다른 잔디 종자의 개수를 출력한다.


Subtask

# Score Condition
#120

N \le 5000

#230

k_i = k_{i+1} (1 \le i \le N-1)

#350

추가 제한 없음


Example #1

2
1 4 3
2 5 2
0
1

첫 번째 잔디 종자는 두 번째 잔디 종자와 r_1 - ℓ_2 = 4 - 2 = 2 만큼 겹친다.


Example #2

4
4 7 1
3 6 1
5 11 1
2 5 1
3
3
2
2

Example #3

5
9 11 2
5 10 2
4 8 4
6 8 1
3 8 1
0
3
1
3
3

Example #4

2
0 16 16
1 3 2
0
1


Source

USACO 2024 US Open Gold 2번

You must sign in to write code.