题目描述

两个 \(d\) 维向量 \(A=[a_1,a_2,\cdots,a_d]\) 与 \(B=[b_1,b_2,\cdots,b_d]\) 的内积为其相对应维度的权值的乘积和，即：

\((A,B)= \sum_{i=1}^d a_ib_i = a_1 b_1 + a_2 b_2 + \cdots + a_d b_d\)

现有 \(n\) 个 \(d\) 维向量 \(x_1,x_2, \cdots, x_n\)，小喵喵想知道是否存在两个向量的内积为 \(k\) 的倍数。

请帮助她解决这个问题。

输入

第一行，包含 \(3\) 个正整数 \(n,d,k\)，分别表示向量的个数，维数以及待检测的倍数。

接下来 \(n\) 行，每行有 \(d\) 个非负整数，其中第 \(i\) 行的第 \(j\) 个整数表示向量 \(x_i\) 的第 \(j\) 维权值 \(x_{i,j}\)。

输出

包含两个整数，用空格隔开。

如果存在两个向量 \(x_p\),\(x_q\) 的内积为 \(k\) 的整数倍，则输出两个向量的编号 \(p\) 与 \(q\)（要求 \(p < q\)）。

如果存在多组这样的向量组合，输出其中任意一组即可。

若不存在这样的向量组合，则输出两个 -1。

样例 1

输入

3 5 2
1 0 1 0 1
1 1 0 1 0
0 1 0 1 1

输出

2 3

说明

\((x_1,x_2)=1\)
\((x_1,x_3)=1\)
\((x_2,x_3)=1\)

数据范围限制

数据范围

测试点编号	\(n\)	\(d\)	\(k\)	\(x_{i,j}\)
\(1\)	\(2\)	\(20\)	\(2\)	\(\leq 10\)
\(2\)	\(5\)	\(20\)	\(2\)	\(\leq 10\)
\(3\)	\(10\)	\(20\)	\(3\)	\(\leq 10\)
\(4\)	\(20\)	\(20\)	\(2\)	\(\leq 100\)
\(5\)	\(50\)	\(20\)	\(3\)	\(\leq 100\)
\(6\)	\(50\)	\(50\)	\(2\)	\(\leq 10^3\)
\(7\)	\(50\)	\(50\)	\(3\)	\(\leq 3\times 10^6 \)
\(8\)	\(80\)	\(80\)	\(2\)	\(\leq 2\times 10^6 \)
\(9\)	\(100\)	\(100\)	\(3\)	\(\leq 3\times 10^6 \)
\(10\)	\(500\)	\(100\)	\(3\)	\(\leq 3\times 10^6\)
\(11\)	\(10^3\)	\(100\)	\(2\)	\(\leq 2\times 10^6\)
\(12\)	\(10^3\)	\(100\)	\(3\)	\(\leq 3\times 10^6\)
\(13\)	\(10^4\)	\(100\)	\(2\)	\(<10\)
\(14\)	\(10^4\)	\(100\)	\(3\)	\(<10\)
\(15\)	\(1.5\times 10^4\)	\(100\)	\(2\)	\(<10\)
\(16\)	\(1.8\times 10^4\)	\(100\)	\(2\)	\(<10\)
\(17\)	\(2\times 10^4\)	\(100\)	\(2\)	\(<10\)
\(18\)	\(5\times 10^4\)	\(30\)	\(3\)	\(<10\)
\(19\)	\(8\times 10^4\)	\(30\)	\(3\)	\(<10\)
\(20\)	\(10^5\)	\(30\)	\(3\)	\(<10\)

限制

每个测试点时限：5秒
内存限制：256MB

来源

NOI2013 D1T1