Məsələlər
Горный пейзаж
Горный пейзаж
Вы путешествуете по живописному ландшафту, состоящему в основном из гор --- на вашем пути есть $n$ ориентиров (пики и долины). Вы останавливаетесь, чтобы перевести дух, и задаетесь вопросом: какую гору вы сейчас видите на горизонте?
\includegraphics{https://static.eolymp.com/content/6d/6db0584145bbb05bdec7ef5840d57e6cf12f0142.gif}
Вам дана полигональная цепочка $P_1P_2...P_n$ на плоскости. Координаты $x$ точек расположены в строго возрастающем порядке. Для каждого сегмента $P_iP_{i+1}$ этой цепочки найдите наименьший индекс $j > i$, для которого некоторая точка $P_jP_{j+1}$ видна из $P_iP_{i+1}$ (лежит строго над лучом $P_iP_{i+1}$).
\InputFile
Первая строка содержит количество тестов $T$.
Первая строка каждого теста содержит целое число $n\:(2 \le n \le 10^5)$ --- количество вершин на цепи. Каждая из следующих $n$ строк содержит целочисленные координаты $x_i, y_i$ вершины $P_i\:(0 \le x_1 < x_2 <... < x_n \le 10^9, 0 \le y_i \le 10^9)$.
\OutputFile
Для каждого теста выведите одну строку, содержащую $n - 1$ целых чисел. Это должны быть наименьшие индексы сегментов цепочки, видимых справа, или $0$, если такой сегмент не существует.
Giriş verilənləri #1
2 8 0 0 3 7 6 2 9 4 11 2 13 3 17 13 20 7 7 0 2 1 2 3 1 4 0 5 2 6 1 7 3
Çıxış verilənləri #1
0 3 6 5 6 0 0 6 4 4 0 6 0