IP Network Address

Interview

Time limit2sMemory limit128 MB

Summary
Given a list of IPv4 addresses, compute the smallest common network address and its mask that covers them all using bitwise operations.
Level

Easy3 of 10

Topics
Bit manipulation, Implementation
Solved
No attempts yet

Problem

Computers in an IP network each have one IPv4 address. An IP network is represented by a network address and a network mask.

An IPv4 address, a network address, and a network mask are written as four decimal bytes separated by dots. Each byte is between 0 and 255, and no byte has leading zeros.

If each byte is written as 8 binary bits and the four bytes are concatenated, an address can be viewed as a 32-bit value. If a network contains 2m2^m addresses, the first 32−m32-m bits of the network address are fixed and the last mm bits are 0. The network mask has 1 in the first 32−m32-m bits and 0 in the last mm bits. The network contains every IP address whose first 32−m32-m bits equal the network address.

You are given IP addresses that all belong to the same network. Print the network address and network mask for the smallest network that contains all given addresses.

Input

The first line contains an integer nn (1≤n≤1,0001 \le n \le 1{,}000). Each of the next nn lines contains one computer's IPv4 address.

Output

Print the network address on the first line and the network mask on the second line.

Examples1

  1. Example 1

    Input
    3
194.85.160.177
194.85.160.183
194.85.160.178
    Expected output
    194.85.160.176
255.255.255.248