The problem uses a simplified TCP/IP address model, please make sure you've read the statement attentively.

Polycarpus has found a job, he is a system administrator. One day he came across n IP addresses. Each IP address is a 32 bit number, represented as a group of four 8-bit numbers (without leading zeroes), separated by dots. For example, the record 0.255.1.123 shows a correct IP address and records 0.256.1.123 and 0.255.1.01 do not. In this problem an arbitrary group of four 8-bit numbers is a correct IP address.

Having worked as an administrator for some time, Polycarpus learned that if you know the IP address, you can use the subnet mask to get the address of the network that has this IP addess.

The subnet mask is an IP address that has the following property: if we write this IP address as a 32 bit string, that it is representable as "11...11000..000". In other words, the subnet mask first has one or more one bits, and then one or more zero bits (overall there are 32 bits). For example, the IP address 2.0.0.0 is not a correct subnet mask as its 32-bit record looks as 00000010000000000000000000000000.

To get the network address of the IP address, you need to perform the operation of the bitwise "and" of the IP address and the subnet mask. For example, if the subnet mask is 255.192.0.0, and the IP address is 192.168.1.2, then the network address equals 192.128.0.0. In the bitwise "and" the result has a bit that equals 1 if and only if both operands have corresponding bits equal to one.

Now Polycarpus wants to find all networks to which his IP addresses belong. Unfortunately, Polycarpus lost subnet mask. Fortunately, Polycarpus remembers that his IP addresses belonged to exactly k distinct networks. Help Polycarpus find the subnet mask, such that his IP addresses will belong to exactly k distinct networks. If there are several such subnet masks, find the one whose bit record contains the least number of ones. If such subnet mask do not exist, say so.


-----Input-----

The first line contains two integers, n and k (1 ≤ k ≤ n ≤ 10^5) — the number of IP addresses and networks. The next n lines contain the IP addresses. It is guaranteed that all IP addresses are distinct.


-----Output-----

In a single line print the IP address of the subnet mask in the format that is described in the statement, if the required subnet mask exists. Otherwise, print -1.


-----Examples-----
Input
5 3
0.0.0.1
0.1.1.2
0.0.2.1
0.1.1.0
0.0.2.3

Output
255.255.254.0
Input
5 2
0.0.0.1
0.1.1.2
0.0.2.1
0.1.1.0
0.0.2.3

Output
255.255.0.0
Input
2 1
255.0.0.1
0.0.0.2

Output
-1

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Implementation

Complete search


Solutions:
import sys
(n, k) = map(int, input().split())
mvals = []
for _ in range(n):
	(x, y, z, w) = map(int, input().split('.'))
	mvals.append(x << 24 | y << 16 | z << 8 | w)
mv = (1 << 32) - 1
for ind in range(31, 0, -1):
	st = set()
	mask = mv - ((1 << ind) - 1)
	for i in range(n):
		st.add(mask & mvals[i])
	if len(st) == k:
		(x, y, z, w) = (mask >> 24, (mask >> 16) % 256, (mask >> 8) % 256, mask % 256)
		print(f'{str(x)}.{str(y)}.{str(z)}.{str(w)}')
		exit()
print(-1)


def parse(ip_address):
	(a, b, c, d) = [int(x) for x in ip_address.split('.')]
	return a << 24 | b << 16 | c << 8 | d
(n, k) = [int(x) for x in input().split()]
ips = [parse(input()) for i in range(n)]
all_ones = (1 << 32) - 1
eight_ones = (1 << 8) - 1
for n_zeros in range(31, 0, -1):
	mask = all_ones << n_zeros
	if len(set((mask & ip for ip in ips))) == k:
		address = [mask >> 24 & eight_ones, mask >> 16 & eight_ones, mask >> 8 & eight_ones, mask & eight_ones]
		print('.'.join((str(x) for x in address)))
		return
print(-1)


import math
import re
from fractions import Fraction
from collections import Counter

class Task:
	ips = []
	k = 0
	answer = ''

	def __init__(self):
		(n, self.k) = [int(x) for x in input().split()]
		self.ips = ['' for _ in range(n)]
		for i in range(len(self.ips)):
			self.ips[i] = input()

	def solve(self):
		(ips, k) = (self.ips, self.k)
		ipAsNumbers = []
		for currentIp in ips:
			number = 0
			parts = currentIp.split('.')
			for i in range(0, len(parts)):
				number += int(parts[i]) * 2 ** (32 - (i + 1) * 8)
			ipAsNumbers += [number]
		mask = 0
		for i in range(31, -1, -1):
			mask += 2 ** i
			netAddresses = set()
			for ip in ipAsNumbers:
				netAddresses.add(mask & ip)
			if len(netAddresses) == k:
				mask = bin(mask)[2:]
				self.answer = '.'.join([str(int(mask[i:i + 8], 2)) for i in range(0, len(mask), 8)])
				return
		self.answer = '-1'

	def printAnswer(self):
		print(self.answer)
task = Task()
task.solve()
task.printAnswer()


def f(t):
	(a, b, c, d) = map(int, t.split('.'))
	return d + (c << 8) + (b << 16) + (a << 24)

def g(x):
	p = [0] * 4
	for i in range(4):
		p[3 - i] = str(x % 256)
		x //= 256
	return '.'.join(p)
(n, k) = map(int, input().split())
t = [f(input()) for i in range(n)]
p = [0] * n
x = 1 << 31
for i in range(32):
	for (j, y) in enumerate(t):
		if y & x:
			p[j] += x
	if len(set(p)) >= k:
		break
	x >>= 1
print(-1 if len(set(p)) != k else g((1 << 32) - x))


import sys, io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k) = map(int, input().decode().split())
mvals = []
for _ in range(n):
	(x, y, z, w) = map(int, input().decode().split('.'))
	mvals.append(x << 24 | y << 16 | z << 8 | w)
mv = (1 << 32) - 1
for ind in range(31, 0, -1):
	st = set()
	mask = mv - ((1 << ind) - 1)
	for i in range(n):
		st.add(mask & mvals[i])
	if len(st) == k:
		(x, y, z, w) = (mask >> 24, (mask >> 16) % 256, (mask >> 8) % 256, mask % 256)
		print(f'{str(x)}.{str(y)}.{str(z)}.{str(w)}')
		exit()
print(-1)