IPAM

Micetro는 Eggert와 Indriði가 Men & Mice에서 개발하는 소프트웨어이다.

Indriði와 Eggert는 DNS 전문가이다. 그들은 Domain Name Servers 관리를 지원하는 소프트웨어를 작성했다. 이 소프트웨어는 역방향 포인터 레코드까지 관리할 수 있다.

이제 그들은 IP Address Management용 소프트웨어를 설계하려고 한다. 네트워크는 IP 주소를 사용한다. 이러한 네트워크를 관리하는 네트워크 관리자들은 IP 주소를 여러 가지 다양한 방식으로 분류하려고 한다. 예를 들어 국가, 도시, 주소, 방 또는 좌표 등 물리적 위치에 따라 분류하는 것이 일반적이다.

소프트웨어는 IP 주소에 속성을 부여할 수 있어야 한다. Indriði와 Eggert는 설계를 완성했다. 두 사람 모두 긴 휴가를 떠나지만, 설계 문서는 여러분에게 맡긴다.

사용자 정의 속성을 분류에 사용해야 한다. 각 속성은 속성의 이름 및 속성의 값과 함께 IP 주소에 부여된다.

사용자는 속성 정의를 생성하는 연산을 사용할 수 있어야 한다. 이 연산에서 사용자는 속성의 이름과 속성의 기본값을 제공한다. 이는 특정 IP 주소에서 해당 속성의 값이 설정되지 않았다면 기본값이 그 주소에 부여된다는 뜻이다. 기존 속성의 기본값을 갱신하기 위해 이 연산을 다시 호출할 수도 있다.

마찬가지로 사용자는 속성 정의를 제거하는 연산을 사용할 수 있어야 한다. 이 연산은 속성의 이름을 입력으로 받아 해당 속성의 정의를 삭제한다. 그 결과 모든 IP 주소에서 해당 속성이 제거된다.

사용자는 IP 주소에 속성을 설정하는 연산을 사용할 수 있어야 한다. 사용자는 연속된 IP 주소 범위, 속성의 이름, 그리고 그 속성에 대응하는 값을 제공할 수 있다. 그러면 범위 내의 각 IP 주소에 해당 속성이 설정된다.

사용자는 IP 주소의 모든 속성을 가져오는 연산을 사용할 수 있어야 한다. 이 연산은 하나의 IP 주소를 입력으로 받아 해당 IP 주소에 부여된 모든 속성을 가져온다.

Eggert와 Indriði는 내일 휴가에서 돌아오므로, 여러분은 근무일이 끝나기 전에 소프트웨어 구현을 완료해야 한다!

채점

그룹 | 점수 | 제약 조건

1 | 30 | $1 \leq q \leq 1\,000$, "10.0.0."로 시작하는 IPv4 숫자만 사용한다.

2 | 25 | $1 \leq q \leq 1\,000$, "10.0."로 시작하는 IPv4 숫자만 사용한다.

3 | 20 | $1 \leq q \leq 1\,000$, "10."로 시작하는 IPv4 숫자만 사용한다.

4 | 15 | $1 \leq q \leq 1\,000$, IPv4 숫자만 사용한다.

5 | 10 | $1 \leq q \leq 10\,000$.

입력의 첫째 줄에 수행할 연산의 수를 나타내는 정수 하나 $q$이 주어진다.

이어서 $q$개의 연산이 주어지며, 각 연산은 입력의 한 줄로 표현된다. 연산은 다음과 같다.

• 정의: 형식은 "+ k v"이다. 여기서 k는 속성의 이름을 나타내고, v는 속성 정의와 관련된 기본값을 나타낸다.

• 제거: 형식은 "- k"이며, k는 제거할 속성의 이름을 나타낸다.

• 설정: 형식은 "= a b k v"이며, a와 b는 각각 범위의 시작 및 끝 IP 주소를 나타낸다. k는 속성의 이름을 나타내고, v는 속성의 값을 나타낸다.

• 가져오기: 형식은 "? x"이며, x는 모든 속성을 가져올 IP 주소를 나타낸다.

다음을 가정해도 좋다.

• 각 속성의 이름은 적어도 $1$자, 최대 $10$자의 영문자, 숫자, 밑줄 또는 하이픈으로 이루어진 문자열이다.

• 각 속성의 값은 적어도 $1$자, 최대 $10$자의 영문자, 숫자, 밑줄 또는 하이픈으로 이루어진 문자열이다.

• 연산 수행 시점에 존재하지 않는 속성 이름을 참조하는 연산은 속성 정의를 생성하는 연산뿐이다.

• 각 IP 주소는 올바른 IPv4 주소이거나 올바른 IPv6 주소이다.

아래에서 IP 주소 형식에 관한 자세한 설명을 확인할 수 있다.

IPv4

IPv4 주소는 네 부분으로 이루어진다. 각 부분은 $0$ 이상 $255$ 이하의 정수이다. 이 부분들은 마침표 하나로 구분된다.

올바른 IPv4 주소의 예시는 다음과 같다.

• 10.100.80.13

• 255.255.255.255

• 255.160.134.0

올바르지 않은 IPv4 주소의 예시는 다음과 같다.

• 300.1.35.28

• 255.255.255.254.1

• 127,0,0,1

IPv6

IPv6 주소는 여덟 부분으로 이루어진다. 각 부분은 네 자리의 십육진수이다. 이 십육진수에는 $0$부터 $9$까지의 숫자와 $a$부터 $f$까지의 문자를 사용한다. 여덟 부분은 콜론 하나씩으로 구분된다. 각 부분에서 수 앞쪽의 영을 생략하여 표기할 수 있다. 인접한 둘 이상의 부분이 $0$만을 포함한다면 그 부분들을 생략하고 그 자리에 콜론 두 개를 쓸 수 있다. 이러한 생략은 IP 주소에서 단 한 곳에만 사용할 수 있다.

올바른 IPv6 주소의 예시는 다음과 같다.

• ffff:dead:1337:beef:4321:f33d:2f92:3419

• 2001:db8:0:0:0:ff00:42:8329

• ::1

• abcd:1234::bad:dad

올바르지 않은 IPv6 주소의 예시는 다음과 같다.

• 0123:4567:89ab:cdef:ghij:klmn:opqr:stuv

• ffff:1234::f6b90::abcd

• 2001:db8:0:0:0:ff00:42:8329:1234

• 1::3::f

IPv4 주소를 IPv6 주소로 표기할 수도 있음에 유의하라. 이는 IPv4 수의 각 부분을 십육진수로 변환하고 변환한 부분들 앞에 ::ffff:을 접두사로 붙여 표기하는 방식이다. 예를 들어, 12.34.56.78은 ::ffff:c22:384e으로 표기할 수 있다.

속성을 가져오는 각 연산마다 먼저 주어진 IP 주소의 속성 수를 나타내는 정수 $k$을 한 줄에 출력한다. 그다음 $k$개의 줄을 출력하며, 각 줄에는 속성의 이름과 값을 공백으로 구분하여 출력한다. 속성은 이름을 기준으로 알파벳순으로 출력해야 한다. 프로그램이 $300\,000$개보다 많은 속성을 출력해야 하는 경우는 없다고 가정해도 좋다.