eolymp
bolt
Try our new interface for solving problems
Problems

Mountainous landscape

Mountainous landscape

Time limit 3 seconds
Memory limit 128 MiB

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_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}).

Input data

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).

Output data

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.

Examples

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
Source 2014 ACM Central Europe (CERC), Problem B