D. New Year's Problem
binary search; greedy; sortings
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.