### National Olympiad in Informatics, China, 2013

## Day 1, Problem 1 - Inner Product

The inner product (a.k.a. dot product) of two `d`-dimensional vectors `A` = [`a`_{1}, `a`_{2}, …, `a _{d}`] and

`B`= [

`b`

_{1},

`b`

_{2}, …,

`b`] is equal to the sum of products of their corresponding components. Specifically:

_{d}

Given `n` such `d`-dimensional vectors, `x`_{1}, …, `x _{n}`, Little Meow-Meow would like to know if there exists two vectors whose inner product is a multiple of

`k`. Please help her solve this problem.

### Input Format

The first line of input contains 3 positive integers `n`, `d`, and `k`, respectively representing the number of vectors, the number of dimensions, and the number of which a inner product could be a multiple.

The next `n` lines each contains `d` nonnegative integers. On the `i`-th of these lines, the `j`-th integer represents `x _{i,j}`, the

`j`-th component of vector

`x`.

_{i}### Output Format

Output two integers, separated by a space.

If there exists two vectors `x _{p}` and

`x`whose inner product is an integer multiple of

_{q}`k`, then output their indices

`p`and

`q`(

`p`<

`q`). 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

### Explanation

(`x`_{1}, `x`_{2}) = 1

(`x`_{1}, `x`_{3}) = 1

(`x`_{2}, `x`_{3}) = 2

### Constraints

Test Case | n | d | k | x_{i,j} |
---|---|---|---|---|

1 | 2 | 20 | 2 | ≤ 10 |

2 | 5 | 20 | 2 | ≤ 10 |

3 | 10 | 20 | 3 | ≤ 10 |

4 | 20 | 20 | 2 | ≤ 100 |

5 | 50 | 20 | 3 | ≤ 100 |

6 | 50 | 50 | 2 | ≤ 1000 |

7 | 50 | 50 | 3 | ≤ 3000000 |

8 | 80 | 80 | 2 | ≤ 2000000 |

9 | 100 | 100 | 3 | ≤ 3000000 |

10 | 500 | 100 | 3 | ≤ 3000000 |

11 | 1000 | 100 | 2 | ≤ 2000000 |

12 | 1000 | 100 | 3 | ≤ 3000000 |

13 | 10000 | 100 | 2 | < 10 |

14 | 10000 | 100 | 3 | < 10 |

15 | 15000 | 100 | 2 | < 10 |

16 | 18000 | 100 | 2 | < 10 |

17 | 20000 | 100 | 2 | < 10 |

18 | 50000 | 30 | 3 | < 10 |

19 | 80000 | 30 | 3 | < 10 |

20 | 100000 | 30 | 3 | < 10 |

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 5.00s

**Memory Limit:** 256M

**Added:** May 18, 2015

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

aintaon Dec 25, 2019 - 5:31:38 pm UTC Test cases are weak?5 3 3

1 1 1

1 1 1

1 1 1

1 1 1

0 0 1

Alexon May 18, 2015 - 2:24:29 am UTC Cautionsimp1etonon Sep 15, 2015 - 12:29:47 am UTC Re: Cautionyingtedon Sep 15, 2015 - 12:32:10 am UTC Re: Cautionxiaowuc1on Sep 15, 2015 - 1:38:30 am UTC Re: CautionAlexon Sep 17, 2015 - 4:36:07 pm UTC Re: Caution