UOJ Logo Universal Online Judge

UOJ

#121. 【NOI2013】向量内积

附件下载 统计

两个 d 维向量 A=[a1,a2,,ad]B=[b1,b2,,bd] 的内积为其相对应维度的权值的乘积和,即:

A,B=i=1daibi=a1b1+a2b2++adbd

现在有 nd 维向量 x1,x2,,xn,小喵喵想知道是否存在两个向量的内积为 k 的倍数。请帮助她解决这个问题。

输入格式

第一行包含 3 个正整数 n,d,k,分别表示向量的个数,维数以及待检测的倍数。

接下来 n 行每行有 d 个非负整数,其中第 i 行的第 j 个整数表示向量 xi 的第 j 维权值 xi,j

输出格式

包含两个整数,用空格隔开。

如果存在两个向量 xp,xq 的内积为 k 的整数倍,则输出两个向量的编号 pq (要求 p<q)。如果存在多组这样的向量组合,输出其中任意一组即可。

若不存在这样的向量组合,则输出两个 1

样例一

input

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

output

2 3

explanation

x1,x2=1x1,x3=1x2,x3=2

限制与约定

测试点编号 n d k xi,j
1220210
2520210
31020310
420202100
550203100
6505021000
7505033000000
8808023000000
910010033000000
1050010033000000
11100010023000000
12100010033000000
13100001002<10
14100001003<10
15150001002<10
16180001002<10
17200001002<10
1850000303<10
1980000303<10
20100000303<10

时间限制:5s

空间限制:256MB

下载

样例数据下载