내적

시간 제한5초메모리 제한512 MB

요약

n개의 d차원 음이 아닌 정수 벡터와 정수 k가 주어질 때, 내적이 k의 배수인 두 벡터의 번호를 찾거나 그런 쌍이 없다고 출력합니다.

난이도: 어려움10점 중 8점
유형: 행렬, 정수론, 수학
정답자: 아직 제출이 없습니다

문제

두 $d$ 차원 벡터 $A = (a_1, a_2, \ldots, a_d)$ 와 $B = (b_1, b_2, \ldots, b_d)$ 의 내적(점곱이라고도 함)은 대응하는 성분끼리 곱한 값을 모두 더한 것이다. $n$ 개의 $d$ 차원 벡터 $x_1, \ldots, x_n$ 이 주어진다. 리틀 미야미야는 내적이 $k$ 의 배수가 되는 벡터 쌍이 있는지 알고 싶어 한다. 이 문제를 풀어 달라.

입력

첫 줄에 양의 정수 $n$ , $d$ , $k$ 가 공백으로 구분되어 주어진다. 각각 벡터의 개수, 차원의 수, 내적이 배수인지 확인할 때 쓰는 수다.

다음 $n$ 개의 줄에는 각각 $d$ 개의 음이 아닌 정수가 주어진다. $i$ 번째 줄의 $j$ 번째 정수는 벡터 $x_i$ 의 $j$ 번째 성분 $x_{i,j}$ 이다.

출력

두 정수를 공백으로 구분하여 출력한다.

내적이 $k$ 의 배수인 벡터 $x_p$ 와 $x_q$ 가 존재하면 그 인덱스 $p$ , $q$ 를 출력한다 ( $p < q$ ). 답이 여러 개이면 그중 아무거나 하나를 출력한다.

그런 쌍이 없으면 $-1$ 을 공백으로 구분하여 두 번 출력한다.

제한

테스트 케이스	$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

예제1

예제 1

입력

예상 출력

2 3