10503번 - 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₁P₂ . . . 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).

입력

The first line of input 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 ≤ n ≤ 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 ≤ x₁ < x₂ < . . . < x_n ≤ 10⁹; 0 ≤ y_i ≤ 10⁹).

출력

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.

제한

힌트