National Olympiad in Informatics, China, 2013
The inner product (a.k.a. dot product) of two -dimensional vectors and is equal to the sum of products of their corresponding components. Specifically:
Given such -dimensional vectors, , Little Meow-Meow would like to know if there exists two vectors whose inner product is a multiple of . Please help her solve this problem.
The first line of input contains positive integers , , and ,
respectively representing the number of vectors, the number of
dimensions, and the number of which a inner product could be a
The next lines each contains nonnegative integers. On the -th of these lines, the -th integer represents , the -th component of vector .
Output two integers, separated by a space.
If there exists two vectors and whose inner product is an integer multiple of , then output their indices and . If there are multiple answers, output any one of them.
If an answer does not exist, then output two
-1's separated by a
3 5 2 1 0 1 0 1 1 1 0 1 0 0 1 0 1 1