Олимпийские игры только что начались, и Федерико с нетерпением ждет начала марафонского забега.
В марафоне будут участвовать \(n\) спортсменов, от \(1\) до \(n\), и все они в прошлом участвовали в \(5\) важных марафонах, пронумерованных от \(1\) до \(5\). Для каждого \(1\le i\le n\) и \(1\le j\le 5\) Федерико помнит, что спортсмен \(i\) занял место \(r_{i,j}\) в марафоне \(j\) (например, \(r_{2,4}=3\) означает, что спортсмен \(2\) был третьим в марафоне \(4\)).
Федерико считает, что спортсмен \(x\) превосходит спортсмена \(y\), если спортсмен \(x\) занял лучшее место, чем спортсмен \(y\), по крайней мере в \(3\) прошлых марафонах, т.е. \(r_{x,j}<r_{y,j}\) по крайней мере для \(3\) различных значений \(j\).
Федерико считает, что у спортсмена хорошие шансы получить золотую медаль на Олимпийских играх, если он превосходит всех остальных спортсменов.
Найдите любого спортсмена, у которого хорошие шансы получить золотую медаль (то есть спортсмена, который превосходит всех остальных спортсменов), или определите, что такого спортсмена нет.
Входные данные
Первая строка содержит одно целое число \(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\). Если таких спортсменов больше, чем один, выведите любого из них.
Примечание
Объяснение первого набора входных данных: Есть только один спортсмен, поэтому он превосходит всех остальных (так как больше никого нет), и поэтому у него хорошие шансы получить золотую медаль.
Пояснение второго набора входных данных: Есть \(n=3\) спортсменов.
- Спортсмен \(1\) превосходит спортсмена \(2\). Действительно, спортсмен \(1\) лучше спортсмена \(2\) в марафонах \(1\), \(2\) и \(3\).
- Спортсмен \(2\) превосходит спортсмена \(3\). Действительно, спортсмен \(2\) превосходит спортсмена \(3\) в марафонах \(1\), \(2\), \(4\) и \(5\).
- Спортсмен \(3\) превосходит спортсмена \(1\). Действительно, спортсмен \(3\) лучше, чем спортсмен \(1\) в марафонах \(3\), \(4\) и \(5\).
Объяснение третьего набора входных данных: Есть \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
5
|