Беси посадила траву на положительной вещественной прямой.
У неё есть \(N\) (\(2\le N\le 2\cdot 10^5\)) различных сортов травы.
И она посадит траву \(i\)-го сорта на интервале
\([\ell_i, r_i]\) (\(0 < \ell_i < r_i \leq 10^9\)).
Известно, что сорт \(i\) растёт лучше, если есть некоторый сорт \(j\)
(\(j\neq i\)) такой, что сорт \(j\) и сорт \(i\) перекрываются на длину
не менее \(k_i\) (\(0 < k_i \leq r_i - \ell_i\)). Беси хочет для каждого
сорта \(i\) вычислить количество таких of \(j\neq i\), что сорты \(j\) и \(i\)
перекрываются на длину не менее \(k_i\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит число
\(N\).
Каждая из последующих \(N\) строк содержит три разделённых одиночными пробелами
целых числа \(\ell_i\), \(r_i\), \(k_i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Ответы для всех сортов на отдельных строках.
SCORING:
- Тесты 4-5: \(N \leq 5000\)
- Тесты 6-11: \(k\) одинаковое для всех интервалов
- Тесты 12-20: Нет дополнительных ограничений..
В дополнение, в тестах 5, 7, ..., 19, \(r_i \leq 2N\) for all \(i\).