## NOI '13 P1 - Inner Product

View as PDF

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 256M

Problem type
##### 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.

#### Input Specification

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 multiple.
The next lines each contains nonnegative integers. On the -th of these lines, the -th integer represents , the -th component of vector .

#### Output Specification

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 space.

#### Sample Input

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

#### Sample Output

2 3

#### Constraints

Test Case

Problem translated to English by Alex.