Гірський пейзаж#7718
Ви подорожуєте мальовничим ландшафтом, що складається переважно з гір — на вашому шляху є орієнтирів (піки та долини). Ви зупиняєтеся, щоб перевести подих, і задаєтеся питанням: яку гору ви зараз бачите на горизонті?
Вам дано полігональний ланцюжок P_1P_2\dots P_n на площині. Координати точок розташовані в строго зростаючому порядку. Для кожного сегмента P_iP_{i+1} цього ланцюжка знайдіть найменший індекс j > i, для якого деяка точка P_jP_{j+1} видна з P_iP_{i+1} (лежить строго над променем P_iP_{i+1}).
Перший рядок містить кількість тестів .
Перший рядок кожного тесту містить ціле число (2 \le n \le 10^5) — кількість вершин на ланцюжку. Кожен з наступних рядків містить цілочисельні координати x_i, y_i вершини P_i (0 \le x_1 < x_2 < \dots < x_n \le 10^9,\, 0 \le y_i \le 10^9).
Для кожного тесту виведіть один рядок, що містить n - 1 цілих чисел. Це повинні бути найменші індекси сегментів ланцюжка, видимих справа, або , якщо такий сегмент не існує.
Приклад 1