시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 67 | 14 | 9 | 28.125% |
The inner product (a.k.a. dot product) of two d-dimensional vectors A = [a1, a2, …, ad] and B = [b1, b2, …, bd] is equal to the sum of products of their corresponding components. Given n such d-dimensional vectors, x1, …, xn, 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.
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 xi,j, the j-th component of vector xi.
Output two integers, separated by a space.
If there exists two vectors xp and xq whose inner product is an integer multiple of 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.
Test Case |
n | d | k | xi,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 |
3 5 2 1 0 1 0 1 1 1 0 1 0 0 1 0 1 1
2 3