Description

你正在穿越一个以山脉为主的风景区——在你的路径上有 $n$ 个地标（山峰和山谷）。你停下来喘口气，想知道：你现在在地平线上看到的是哪座山？

正式地说：给定一个平面上的多边形链 $P_1,P_2,\cdots,P_n$。这些点的 $x$ 坐标是严格递增的。对于这条链的每一段 $P_i P_{i+1}$，找出最小的索引 $j > i$，使得 $P_j P_{j+1}$ 上的至少一个点从 $P_i P_{i+1}$ 可见（严格位于射线 $P_i \ P^{\rightarrow}_{i+1}$ 之上）。

Input Format

输入的第一行包含测试用例的数量 $T$。接下来的部分是测试用例的描述：

每个测试用例的第一行包含一个整数 $n(2 \le n \le 100 000)$——链上的顶点数量。

接下来的 $n$ 行中的每一行包含顶点 $P_i$ 的整数坐标 $x_i, y_i (0 \le x_1 < x_2 < \cdots < x_n \le 10^9, 0 \le y_i \le 10^9)$。

Output Format

对于每个测试用例，输出一行包含 $n-1$ 个以空格分隔的整数。这些应该是向右可见的链段的最小索引，或者当不存在这样的链段时为 $0$。

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

Hint

题面翻译由 ChatGPT-4o 提供。