Description

{{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.}}

Input Format

{{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 Format

{{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<q$). If there are multiple valid pairs, output any one of them.

If no such pair exists, output two $-1$.}}

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

2 3

Hint

{{### Constraints

Test point ID	$n$	$d$	$k$	$x_{i,j}$
$1$	$2$	$20$	$2$	$\leq 10$
$2$	$5$	^		^
$3$	$10$	$20$	$3$
$4$	$20$		$2$	$\leq 100$
$5$	$50$		$3$	^
$6$		$50$	$2$	$\leq 10^3$
$7$			$3$	$\leq 3\times 10^6$
$8$	$80$		$2$	$\leq 2\times 10^6$
$9$	$100$		$3$	$\leq 3\times 10^6$
$10$	$500$	^	^
$11$	$10^3$		$2$	$\leq 2\times 10^6$
$12$			$3$	$\leq 3\times 10^6$
$13$	$10^4$		$2$	$<10$
$14$			$3$	^
$15$	$1.5\times 10^4$		$2$
$16$	$1.8\times 10^4$		^
$17$	$2\times 10^4$
$18$	$5\times 10^4$	$30$	$3$
$19$	$8\times 10^4$	^
$20$	$10^5$

Translated by ChatGPT 5