P1224 {{[NOI2013] Vector Inner Product}}

{{}}

{{The dot product of two $d$-dimensional vectors $A=[a_1,a_2,\ldots,a_d]$ and $B=[b_1,b_2,\ldots,b_d]$ is the sum of the products of their corresponding coordinates, i.e.: $$(A,B)=\sum_{i=1}^d a_ib_i=a_1b_1+a_2b_2+\ldots+a_db_d$$ Given $n$ $d$-dimensional vectors $x_1,\ldots,x_n$, Xiao Miaomiao (pinyin) wants to know whether there exist two vectors whose dot product is a multiple of $k$. Please help her solve this problem.}}

{{The first line contains $3$ positive integers $n, d, k$, representing the number of vectors, the dimension, and the multiple to check, respectively. The next $n$ lines each contain $d$ non-negative integers. In the $i$-th line, the $j$-th integer is the $j$-th coordinate value $x_{i,j}$ of vector $x_i$.}}

{{Output two integers separated by a space. If there exist two vectors $x_p, x_q$ whose dot product is an integer multiple of $k$, output their indices $p$ and $q$ (require $p

{{### Constraints | Test point ID | $n$ | $d$ | $k$ | $x_{i,j}$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $2$ | $20$ | $2$ | $\leq 10$ | | $2$ | $5$ | ^ | ^ | ^ | | $3$ | $10$ | $20$ | $3$ | ^ | | $4$ | $20$ | $20$ | $2$ | $\leq 100$ | | $5$ | $50$ | $20$ | $3$ | ^ | | $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$ | ^ | ^ | ^ | | $11$ | $10^3$ | ^ | $2$ | $\leq 2\times 10^6$ | | $12$ | $10^3$ | ^ | $3$ | $\leq 3\times 10^6$ | | $13$ | $10^4$ | ^ | $2$ | $