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?

Formally: you are given a polygonal chain $P_1 P_2 \ldots P_ n$ in the plane. The $x$ coordinates of the points are in strictly increasing order. For each segment $P_ i P_{i+1}$ of this chain, find the smallest index $j > i$, for which any point of $P_ j P_{j+1}$ is visible from $P_ i P_{i+1}$ (lies strictly above the ray $\overrightarrow {P_ i P_{i+1}}$ ).

The first line of input contains the number of test cases $T$ ($1 \leq T \leq 10$). The descriptions of the test cases follow:

The first line of each test case contains an integer $n$ ($2 \leq n \leq 100\, 000$)â€”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 \leq x_1 < x_2 < \ldots < x_ n \leq 10^9$; $0 \leq y_ i \leq 10^9$).

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.

Sample Input 1 | Sample Output 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 |
0 3 6 5 6 0 0 6 4 4 0 6 0 |