FRAKTAL - konkurs programistyczny

Nie zna życia ten, kto nie grywał w Ice Tower na szkolnych komputerach w czasie przerwy przed i po lekcji informatyki (w trakcie lekcji także). To prosta gra platformowa, w której skaczesz po platformach, aby dostać się na szczyt bardzo wysokiej wieży.

Jako doświadczony gracz postanawiasz nieco utrudnić sobie wyzwanie (jest za to odpowiednia odznaka w grze).

Przypomnijmy sobie jakie zasady obowiązują:

• Zaczynasz z dowolnej najniżej położonej platformy.
• Celem jest dotarcie na jedną z najwyżej położonych platform wykonując jak najmniej skoków.
• Możesz skakać tylko prosto w górę (nie wolno skręcać w czasie lotu).
• Nie wolno przeskakiwać między platformami na tym samym poziomie.
• Nie wolno schodzić na platformy poniżej tej, na której jesteś obecnie.
• Nie wolno przeskakiwać kilka platform równocześnie. Zawsze wskakujesz na pierwszą platformę wiszącą nad Tobą.
• Możesz skakać dowolnie wysoko (ale tylko do najbliższej platformy nad Tobą).
• Możesz się dowolnie przesuwać w obrębie jednej platformy.

Dla każdej platformy na najwyższym poziomie policz ile najmniej skoków należy wykonać, aby się tam dostać. Jeżeli jest to niemożliwe, wypisz NIE.

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów danych t (0 < t < 10). W kolejnych liniach znajdują się zestawy danych.

W pierwszej linii każdego zestawu danych znajduje się liczba platform n (0 < n < 10⁶).

W kolejnych n liniach znajdują się opisy platform. Platforma opisana jest trzema nieujemnymi wartościami: w, p, k oznaczającymi odpowiednio: wysokość na jakiej się znajduje (w < 10⁵), jej początek i koniec (p, k < 2×10⁷). W obrębie jednej wysokości platformy nie nachodzą na siebie i jest między nimi odstęp co najmniej 1. Platforma ma zawsze niezerową długość (p < k).

Wyjście

Na wyjściu należy wypisać t linii. Każda linia powinna zawierać wynik dla pojedynczego zestawu danych. Wynik dla pojedynczego zestawu danych powinien składać się z wyników dla każdej z najwyżej położonych platform. Wynik dla pojedynczej platformy to minimalna liczba skoków jaką należy wykonać, aby się na nią dostać albo słowo NIE jeżeli jest to niemożliwe. Wyniki dla platform wypisujemy w kolejności rosnących wartości ich początków p.

Przykład

Wejście:

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

Wyjście

1
4 NIE