A14864 | New Year's Problem

Vlad has $n$ friends, for each of whom he wants to buy one gift for the New Year.

There are $m$ shops in the city, in each of which he can buy a gift for any of his friends. If the $j$ -th friend ( $1 \le j \le n$ ) receives a gift bought in the shop with the number $i$ ( $1 \le i \le m$ ), then the friend receives $p_{ij}$ units of joy. The rectangular table $p_{ij}$ is given in the input.

Vlad has time to visit at most $n-1$ shops (where $n$ is the number of friends). He chooses which shops he will visit and for which friends he will buy gifts in each of them.

Let the $j$ -th friend receive $a_j$ units of joy from Vlad's gift. Let's find the value $\alpha=\min\{a_1, a_2, \dots, a_n\}$ . Vlad's goal is to buy gifts so that the value of $\alpha$ is as large as possible. In other words, Vlad wants to maximize the minimum of the joys of his friends.

For example, let $m = 2$ , $n = 2$ . Let the joy from the gifts that we can buy in the first shop: $p_{11} = 1$ , $p_{12}=2$ , in the second shop: $p_{21} = 3$ , $p_{22}=4$ .

Then it is enough for Vlad to go only to the second shop and buy a gift for the first friend, bringing joy $3$ , and for the second — bringing joy $4$ . In this case, the value $\alpha$ will be equal to $\min\{3, 4\} = 3$

Help Vlad choose gifts for his friends so that the value of $\alpha$ is as high as possible. Please note that each friend must receive one gift. Vlad can visit at most $n-1$ shops (where $n$ is the number of friends). In the shop, he can buy any number of gifts.

The first line of the input contains an integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases in the input.

An empty line is written before each test case. Then there is a line containing integers $m$ and $n$ ( $2 \le n$ , $2 \le n \cdot m \le 10^5$ ) separated by a space — the number of shops and the number of friends, where $n \cdot m$ is the product of $n$ and $m$ .

Then $m$ lines follow, each containing $n$ numbers. The number in the $i$ -th row of the $j$ -th column $p_{ij}$ ( $1 \le p_{ij} \le 10^9$ ) is the joy of the product intended for friend number $j$ in shop number $i$ .

It is guaranteed that the sum of the values $n \cdot m$ over all test cases in the test does not exceed $10^5$ .

Print $t$ lines, each line must contain the answer to the corresponding test case — the maximum possible value of $\alpha$ , where $\alpha$ is the minimum of the joys from a gift for all of Vlad's friends.