Problems
Mountainous landscape
Mountainous landscape
You travel through a scenic landscape consisting mostly of mountains --- there are $n$ landmarks (peaks and valleys) on your path. You pause for breath and wonder: which mountain are you currently seeing on the horizon?
\includegraphics{https://static.eolymp.com/content/6d/6db0584145bbb05bdec7ef5840d57e6cf12f0142.gif}
Formally: you are given a polygonal chain $P_1P_2...P_n$ in the plane. The $x$ coordinates of the points are in strictly increasing order. For each segment $P_iP_{i+1}$ of this chain, find the smallest index $j > i$, for which any point of $P_jP_{j+1}$ is visible from $P_iP_{i+1}$ (lies strictly above the ray $P_iP_{i+1}$).
\InputFile
The first line contains the number of test cases $T$. The descriptions of the test cases follow:
The first line of each test case contains an integer $n\:(2 \le n \le 10^5)$ --- the number of vertices on the chain. Each of the following $n$ lines contains integer coordinates $x_i, y_i$ of the vertex $P_i\:(0 \le x_1 < x_2 <... < x_n \le 10^9, 0 \le y_i \le 10^9)$.
\OutputFile
For each test case, output a single line containing $n - 1$ space-separated integers. These should be the smallest indices of chain segments visible to the right, or $0$ when no such segment exists.
Input example #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
Output example #1
0 3 6 5 6 0 0 6 4 4 0 6 0