发现这个内积和矩乘有点像，考虑构造一个 $n$ 行 $m$ 列的矩阵 $A$，每一行都是一个题目给定的 $m$ 维向量
设 $B=AA^T$ ，其中 $A^T$ 为 $A$ 的转置矩阵，那么对于 $B_{i,j}$ 的值，它其实就是向量 $i$ 和向量 $j$ 的内积
注意到 $K$ 只有 $2$ 或 $3$，先考虑 $K=2$ 时的情况
此时就是问矩阵 $B$ 在模 $2$ 意义下是否有位置的值为 $0$ ，并且求出位置
首先判断是否有 $0$ ，因为此时 $B$ 的元素不是 $0$ 就是 $1$ ，所以就是比较 $B$ 和全 $1$ 矩阵 $C$ 是否相等
所以就是要快速判断 $AA^T=C$ ，至于快速判断矩阵乘积结果是否等于给定矩阵，是有套路的
设 $D$ 为 $1$ 行 $n$ 列的随机矩阵，那么如果 $DAA^T \neq DC$ 那么显然 $AA^T \neq C$，否则还有概率是因为 $D$ 的影响才相等，我们多做几次判断即可
这样矩乘的复杂度就会低很多，判断 $DAA^T$ 是否等于 $DC$ 时，如果 $DC$ 的第 $i$ 个位置和 $DAA^T$ 不相等，那么说明向量 $i$ 和某个向量内积不是 $K$ 的倍数，此时我们只要枚举另一个向量 $j$ 并暴力判断即可
对于 $K=3$ 的情况，发现 $B$ 的元素不只是 $0,1$ 还有 $2$ ，似乎没法判断了
但是注意到（我也不知道怎么注意到的） $2^2 \equiv 1 \mod 3,1^2 \equiv 1 \mod 3,0^2 \equiv 0 \mod 3$
所以如果我们能把 $B$ 的每个元素平方，那么 $B$ 就又变成了 $01$ 矩阵，直接枚举元素再平方显然会 $T$ 飞
所以写写式子， $B_{i,j}=A_i \cdot A_j=\sum_{k=1}^{m}A_{i,k} \cdot A_{j,k}$，$(B_{i,j})^2=(\sum_{k=1}^{m}A_{i,k} \cdot A_{j,k})(\sum_{k=1}^{m}A_{i,k} \cdot A_{j,k})$
$(B_{i,j})^2=\sum_{k_1=1}^{m}\sum_{k2=1}^{m}(A_{i,k_1}A_{i,k_2})(A_{j,k_1}A_{j,k_2})$
所以我们把向量变成 $m^2$ 维，$A'_{i,(k_1-1)*m+k_2}=A_{i,k_1} \cdot A_{i,k_2}$
然后就可以用同样的方法判断了，当然 $A'$ 不能直接生成，我们只能存一下 $x=(k_1-1)*m+k_2$ 时的 $k_1,k_2$ 乘的时候再利用 $A_{i,k_1},A_{i,k_2}$ 进行计算
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=1e5+,M=;
int n,m,K;
inline int fk(int x) { return x>=K ? x-K : x; }
int A[N][M],B[N],C[N],D[N];
inline bool check(int i,int j)
{
int res=;
for(int k=;k<=m;k++)
res=fk(res+A[i][k]*A[j][k]%K);
return res==;
}
inline int find(int p)
{
for(int i=;i<=n;i++)
if(i!=p&&check(i,p)) return i;
return ;
}
void solve1()
{
for(int I=;I<=;I++)
{
int tot=;
for(int i=;i<=n;i++) B[i]=rand()&,tot+=B[i];
tot%=K;
for(int i=;i<=m;i++) C[i]=;
for(int i=;i<=n;i++) D[i]=;
for(int i=;i<=m;i++)
for(int j=;j<=n;j++) C[i]+=B[j]*A[j][i];
for(int i=;i<=m;i++) C[i]%=K;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++) D[i]+=C[j]*A[i][j];
D[i]%=K; if(D[i]==tot) continue;
int x=i,y=find(i);
printf("%d %d\n",min(x,y),max(x,y));
return;
}
}
printf("-1 -1\n");
}
int l[N],r[N];
void solve2()
{
int mm=m*m;
for(int i=;i<=mm;i++)
{
int t=i/m+(i%m!=);
l[i]=t; r[i]=i-(t-)*m;
}
for(int I=;I<=;I++)
{
int tot=;
for(int i=;i<=n;i++) B[i]=rand()&,tot+=B[i];
tot%=K;
for(int i=;i<=mm;i++) C[i]=;
for(int i=;i<=n;i++) D[i]=;
for(int i=;i<=mm;i++)
for(int j=;j<=n;j++) C[i]+=B[j]*A[j][l[i]]*A[j][r[i]];
for(int i=;i<=n;i++)
{
for(int j=;j<=mm;j++) D[i]+=C[j]*A[i][l[j]]*A[i][r[j]];
D[i]%=K; if(D[i]==tot) continue;
int x=i,y=find(i);
printf("%d %d\n",min(x,y),max(x,y));
return;
}
}
printf("-1 -1\n");
}
int main()
{
srand();
n=read(),m=read(),K=read();
for(int i=;i<=n;i++)
for(int j=;j<=m;j++) A[i][j]=read()%K;
if(K==) solve1();
else solve2();
return ;
}