시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 0 0 0 0.000%

문제

The inner product (a.k.a. dot product) of two d-dimensional vectors A = [a1a2, …, ad] and B = [b1b2, …, 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 nd, 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

예제 입력 1

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

예제 출력 1

2 3