Educational Codeforces Round 80 (Rated for Div. 2) D. Minimax Problem

题目链接
You are given $n$ arrays $a_1$, $a_2$, …, $a_n$; each array consists of exactly $m$ integers. We denote the $y$-th element of the $x$-th array as $a_{x,y}$.

You have to choose two arrays $a_i$ and $a_j$ ($1\le i,j\le n$, it is possible that $i=j$). After that, you will obtain a new array $b$ consisting of $m$ integers, such that for every $k\in [1,m]$ $b_k=\max (a_{i,k},a_{j,k})$.

Your goal is to choose $i$ and $j$ so that the value of $\underset{k=1}{\overset{m}{\min }}{b}_k$ is maximum possible.

Input

The first line contains two integers $n$ and $m$ ($1\le n\le 3\cdot 10^5$, $1\le m\le 8$) — the number of arrays and the number of elements in each array, respectively.

Then $n$ lines follow, the $x$-th line contains the array $a_x$ represented by $m$ integers $a_{x,1}$, $a_{x,2}$, …, $a_{x,m}$ ($0\le a_{x,y}\le 10^9$).

Output

Print two integers $i$ and $j$ ($1\le i,j\le n$, it is possible that $i=j$) — the indices of the two arrays you have to choose so that the value of $\underset{k=1}{\overset{m}{\min }}{b}_k$ is maximum possible. If there are multiple answers, print any of them.

Example

input

6 5
5 0 3 1 2
1 8 9 1 3
1 2 3 4 5
9 1 0 3 7
2 3 0 6 3
6 4 1 7 0

output

1 5

对$\underset{k=1}{\overset{m}{\min }}{b}_k$进行二分。
设当前值为$mid$,对于矩阵中的某元素$a_{i,j}$，如果$a_{i,j}\ge mid$,则矩阵$c_{i,j}=1$,否则$c_{i,j}=0$。
以$mid=3$为例，样例中的矩阵$a$可以得到矩阵$c$如下:

1 0 1 0 0
0 1 1 0 1
0 0 1 1 1
1 0 0 1 1
0 1 0 1 1
1 1 0 1 0

可以看到，矩阵$c$的第1行和第5行逐列相与结果均为1，因此对于选择第1行和第5行得到的序列$b$，$\underset{k=1}{\overset{m}{\min }}{b}_k\ge mid$。函数$check()$就是寻找对于当前$mid$是否存在行$i$和行$j$，使得矩阵$c$的第$i$行和第$j$行逐列相与结果均为$1$。由于$1\le n\le 3\cdot 10^5$，暴力枚举$i$，$j$会超时,但是由于$1\le m\le 8$，因此可以枚举行$i$，枚举满足条件的行$j$，然后检查是否存在$j$即可。
值得注意的是，由于本题要输出行号$i$，$j$，而不是输出$\underset{k=1}{\overset{m}{\min }}{b}_k$。虽然得到了正确的$\underset{k=1}{\overset{m}{\min }}{b}_k$，但是由于$l=r$跳出二分过程导致$mid=\underset{k=1}{\overset{m}{\min }}{b}_k$的情况没有$check()$更新答案，因此在二分结束后还要$check()$$mid=\underset{k=1}{\overset{m}{\min }}{b}_k$的情况。

#include<bits/stdc++.h>

#define mii unordered_map<int,int>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 3e5 + 10, M = 8;
int a[N][M], n, m, ans1, ans2, now, sta[N];
mii id;

inline void build(int x) {
    id.clear();
    for (int i = 1, res; i <= n; ++i) {
        res = 0;
        for (int j = 0; j < m; ++j)
            if (a[i][j] >= x)res |= 1 << j;
        id[res] = i, sta[i] = res;
    }
}

bool dfs(int x, int u) {
    if (u == m) {
        if (id[x]) {
            ans1 = now, ans2 = id[x];
            return true;
        }
        return false;
    }
    if (!(sta[now] >> u & 1))return dfs(x | (1 << u), u + 1);
    else {
        if (dfs(x, u + 1))return true;
        if (dfs(x ^ (1 << u), u + 1))return true;
        return false;
    }
}

inline bool check() {
    for (int i = 1; i <= n; ++i) {
        now = i;
        if (dfs(0, 0))return true;
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &m);
    int l = INF, r = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < m; ++j) {
            scanf("%d", &a[i][j]);
            l = min(l, a[i][j]);
            r = max(r, a[i][j]);
        }
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        build(mid);
        check() ? l = mid : r = mid - 1;
    }
    build(l), check();
    printf("%d %d\n", ans1, ans2);
    return 0;
}