Inner Product

n개의 d차원 음이 아닌 정수 벡터가 주어질 때 내적이 k의 배수가 되는 두 벡터를 찾아 출력하고, 없으면 -1 -1을 출력한다.

어려움8수학조합론완전 탐색정수론아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제 설명

예제1

문제

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