← 返回题目列表

Codeforces · 291/C

C. 网络掩码

中文机器翻译题面 查看原题

该问题使用了简化的TCP/IP地址模型,请确保您已仔细阅读该声明。

Polycarpus 已找到工作,他是一名系统管理员。有一天,他发现了 n 个 IP 地址。每个 IP 地址都是一个 32 位数字,表示为一组由点分隔的四个 8 位数字(无前导零)。例如,记录 0.255.1.123 显示正确的 IP 地址,而记录 0.256.1.123 和 0.255.1.01 则不显示。在此问题中,任意一组四个 8 位数字就是正确的 IP 地址。

在担任了一段时间的管理员后,Polycarpus 了解到,如果您知道 IP 地址,则可以使用子网掩码来获取具有该 IP 地址的网络地址。

子网掩码是具有以下属性的 IP 地址:如果我们将此 IP 地址写为 32 位字符串,则它可表示为“11...11000..000”。换句话说,子网掩码首先有一个或多个1位,然后有一个或多个0位(总共有32位)。例如,IP 地址 2.0.0.0 不是正确的子网掩码,因为其 32 位记录看起来为 00000010000000000000000000000000。

要获取IP地址的网络地址,需要将IP地址与子网掩码进行按位“与”运算。例如,如果子网掩码为 255.192.0.0,IP 地址为 192.168.1.2,则网络地址等于 192.128.0.0。在按位“与”中,当且仅当两个操作数的对应位都等于 1 时,结果才有一位等于 1。

现在 Polycarpus 想要找到他的 IP 地址所属的所有网络。不幸的是,Polycarpus 丢失了子网掩码。幸运的是,Polycarpus 记得他的 IP 地址恰好属于 k 个不同的网络。帮助 Polycarpus 找到子网掩码,这样他的 IP 地址将恰好属于 k 个不同的网络。如果有多个这样的子网掩码,请找出位记录中包含最少个数的子网掩码。如果这样的子网掩码不存在,请说明。

输入

第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 105) — IP 地址和网络的数量。接下来的 n 行包含 IP 地址。保证所有 IP 地址都是不同的。

输出

如果所需的子网掩码存在,则以语句中描述的格式在单行中打印子网掩码的 IP 地址。否则,打印-1。

示例

输入 #1

5 3
0.0.0.1
0.1.1.2
0.0.2.1
0.1.1.0
0.0.2.3

输出 #1

255.255.254.0

输入 #2

5 2
0.0.0.1
0.1.1.2
0.0.2.1
0.1.1.0
0.0.2.3

输出 #2

255.255.0.0

输入 #3

2 1
255.0.0.1
0.0.0.2

输出 #3

-1