카페 바자르 IP 데이터베이스

카페 바자르는 서버 부하가 커서 성능 최적화와 통계 목적으로 서버 트래픽을 날마다 기록한다. 하루치 로그에 담긴 IP 주소는 아래에 설명하는 두 형식, 곧 IP 구간 형식이나 CIDR 형식 중 하나로 데이터베이스에 저장한다.

IP 데이터베이스 소프트웨어는 IPv5라고 부르는 새 인터넷 프로토콜(IP)을 쓴다. IPv5는 주소 비트 수를 IPv4의 32비트에서 40비트로 늘려 더 많은 주소를 제공한다. IPv5의 IP 주소는 인터넷에 연결된 장치마다 붙는 40비트 수치 라벨이다. 주소 하나는 바이트라고 부르는 수 5개의 나열로 나타내며, 각 바이트는 0부터 255까지의 십진값을 가진다. IP 주소는 보통 점 십진 표기법으로 쓴다. 예를 들어 "134.172.16.254.1"과 같이 다섯 바이트를 십진수로 적고 마침표로 구분한다. 이 표기법에서 앞의 0 바이트는 생략하지 않는다. 예를 들어 수치값이 0인 주소는 "0.0.0.0.0"으로 적는다.

CIDR(Classless Inter-Domain Routing)은 IP 주소의 범위를 지정하는 방법이다. CIDR은 보통의 IP 주소 뒤에 빗금과 수 하나를 붙인 모양이다. CIDR $y/x$에서 $y$는 IP 주소이고 $x$는 0 이상 40 이하의 정수이며, 왼쪽 $x$개 비트가 $y$의 왼쪽 $x$개 비트와 같은 주소 전체의 범위를 뜻한다. 나머지 비트는 0이어도 되고 1이어도 된다. 범위마다 표현을 하나로 정하려고 $y$의 오른쪽 $40 - x$개 비트는 모두 0이어야 한다.

IP 구간 형식은 IP 주소의 범위를 지정하는 또 다른 방법이다. 이 형식의 범위는 첫 주소와 마지막 주소를 점 십진 표기법으로 적고 붙임표(-)로 이어서 나타낸다. IP 주소를 256진법 다섯 자리 수로 볼 때 첫 주소는 마지막 주소보다 크지 않다.

예를 들어 "128.192.168.200.0/32"는 앞 32비트(4바이트 "128.192.168.200")가 범위 안의 모든 주소에서 같고 마지막 바이트만 달라지는 CIDR이다. 같은 범위를 IP 구간 형식으로 쓰면 "128.192.168.200.0-128.192.168.200.255"이다.

세계 곳곳에서 고객이 모이고 여러 해 동안 서비스를 이어 온 탓에 IP 데이터베이스는 점점 커지고 있다. 그래서 카페 바자르는 이미 저장된 범위를 최소 개수의 CIDR로 나타내어 데이터베이스의 항목 수를 줄이려고 한다. 새로 만든 CIDR은 데이터베이스에 속하지 않는 IP 주소를 하나도 포함해서는 안 된다. 이 두 조건을 만족하는 CIDR 집합은 하나뿐이다.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 IP 데이터베이스에 들어 있는 IP 범위의 개수 $n$이 주어진다($1 \le n \le 100$). 이어지는 $n$개 줄에는 IP 범위가 한 줄에 하나씩 CIDR 형식이나 IP 구간 형식으로 주어진다. 입력의 마지막 줄에는 0이 주어지며 이 줄은 처리하지 않는다.

각 테스트 케이스마다 IP 데이터베이스 전체를 나타내는 CIDR의 최소 개수를 한 줄에 출력하고, 이어서 그 CIDR을 IP 값이 커지는 순서로 한 줄에 하나씩 출력한다.