← 返回题目列表

Codeforces · 1552/B

B. 争夺金牌

中文机器翻译题面 查看原题

奥运会刚刚开始,费德里科很想看马拉松比赛。

将有$$$n$$$运动员参加马拉松比赛,编号从$$$1$$$到$$$n$$$,他们都曾参加过$$$5$$$重要的马拉松比赛,编号从$$$1$$$到$$$5$$$。对于每个 $$$1\le i\le n$$$ 和 $$$1\le j\le 5$$$,Federico 记得运动员 $$$i$$$ 在马拉松 $$$j$$$ 中排名第 $$$r_{i,j}$$$(例如,$$$r_{2,4}=3$$$ 意味着运动员 $$$2$$$ 在马拉松比赛中排名第三$$$4$$$)。

如果运动员 $$$x$$$ 在过去至少 $$$3$$$ 的马拉松比赛中排名优于运动员 $$$y$$$,则 Federico 认为运动员 $$$x$$$ 优于运动员 $$$y$$$,即 $$$r_{x,j}<r_{y,j}$$$ 对于 $$$j$$$ 的不同值至少为 $$$3$$$。

费德里科认为,如果一名运动员优于所有其他运动员,他就有可能在奥运会上获得金牌。

查找任何有可能获得金牌的运动员(即优于所有其他运动员的运动员),或确定不存在这样的运动员。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 50\,000$$$) — 运动员的数量。

接下来是 $$$n$$$ 行,每行描述一名运动员的排名位置。

这些行中的第 $$$i$$$ 包含 $$$5$$$ 整数 $$$r_{i,1},\,r_{i,2},\,r_{i,3},\,r_{i,4},\, r_{i,5}$$$ ($$$1\le r_{i,j}\le 50\,000$$$) —运动员$$$i$$$在过去$$$5$$$马拉松比赛中的排名。保证在过去的 $$$5$$$ 马拉松比赛中,$$$n$$$ 运动员具有不同的排名位置,即对于每个 $$$1\le j\le 5$$$,$$$n$$$ 值 $$$r_{1,j},\, r_{2, j},\, \dots,\, r_{n, j}$$$ 是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$50\,000$$$。

输出

对于每个测试用例,打印一个整数 - 有可能获得金牌的运动员的编号(即优于所有其他运动员的运动员)。如果没有这样的运动员,则打印$$$-1$$$。如果这样的运动员不止一名,请打印其中任何一位。

示例

输入 #1

4
1
50000 1 50000 50000 50000
3
10 10 20 30 30
20 20 30 10 10
30 30 10 20 20
3
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
6
9 5 3 7 1
7 4 1 6 8
5 6 7 3 2
6 7 8 8 6
4 2 2 4 5
8 3 6 9 4

输出 #1

1
-1
1
5

注意

第一个测试用例的解释:只有一名运动员,因此他比其他所有人都优越(因为没有其他人),因此他很可能获得金牌。

第二个测试用例的解释:有$$$n=3$$$运动员。

- 运动员 $$$1$$$ 优于运动员 $$$2$$$。事实上,运动员$$$1$$$ 在马拉松$$$1$$$、$$$2$$$ 和$$$3$$$ 比赛中排名优于运动员$$$2$$$。
- 运动员 $$$2$$$ 优于运动员 $$$3$$$。事实上,运动员$$$2$$$ 在马拉松$$$1$$$、$$$2$$$、$$$4$$$ 和$$$5$$$ 中排名优于运动员$$$3$$$。
- 运动员 $$$3$$$ 优于运动员 $$$1$$$。事实上,运动员 $$$3$$$ 在马拉松 $$$3$$$、$$$4$$$ 和 $$$5$$$ 比赛中排名优于运动员 $$$1$$$。

第三个测试用例的解释:有$$$n=3$$$运动员。

- 运动员 $$$1$$$ 优于运动员 $$$2$$$ 和 $$$3$$$。由于他比所有其他运动员都优越,因此他很可能获得金牌。
- 运动员 $$$2$$$ 优于运动员 $$$3$$$。
- 运动员 $$$3$$$ 并不优于任何其他运动员。

第四个测试用例的解释:有$$$n=6$$$运动员。

- 运动员 $$$1$$$ 优于运动员 $$$3$$$、$$$4$$$、$$$6$$$。
- 运动员 $$$2$$$ 优于运动员 $$$1$$$、$$$4$$$、$$$6$$$。
- 运动员 $$$3$$$ 优于运动员 $$$2$$$、$$$4$$$、$$$6$$$。
- 运动员 $$$4$$$ 并不优于任何其他运动员。
- 运动员 $$$5$$$ 优于运动员 $$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$、$$$6$$$。由于他比所有其他运动员都优越,因此他很可能获得金牌。
- 运动员 $$$6$$$ 仅优于运动员 $$$4$$$。