Problem S
IPAM

Micetro is the software Eggert and Indriði develop at Men & Mice.

Indriði and Eggert are DNS experts. They wrote a piece of software that supports management of Domain Name Servers. It can even manage reverse pointer records.

Now they want to design software for IP Address Management. Networks make use of IP addresses. The network administrators that manage these networks want to categorise IP addresses in many different ways. For example, it is common to categorise by physical location, whether it is by country, city, address, room, or coordinates.

The software must be able to attach properties to IP addresses. Indriði and Eggert have finalised a design. They are both going on a long vacation, but they leave the design document in your hands.

Custom properties should be used to categorise. Each property is attached to an IP address with the name of the property and the value of the property.

Users should have access to an operation that creates a property definition. In that operation the user provides the name of the property and a default value for the property. That means if a value has not been set for that particular property on an IP address, the default value will be attached to the address. This operation may be called again for an existing property to update the default value.

Similarly, users should have access to an operation that removes a property definition. The operation takes as input the name of a property and erases the definition of that property. This results in clearing the property away on all IP addresses.

Users should have access to an operation that sets properties on IP addresses. The user can provide a contiguous range of IP addresses, the name of a property and the corresponding value for the property. This will set the property on each IP address in the range.

Users should have access to an operation that gets all properties of an IP address. This operation takes as input a single IP address and fetches all of the properties attached to that particular IP address.

Eggert and Indriði are coming back from their vacation tomorrow, which is why you must finish implementing the software before the end of the workday!

Input

The first line of input contains one integer $q$, the number of operations to perform.

Then $q$ operations follow, where each operation is represented by a single line of input. The operations are:

• Define, in the format "+ k v", where k represents the name of the property and v represents the associated default value for the property definition.

• Remove, in the format "- k", where k represents the name of the property being removed.

• Set, in the format "= a b k v", where a and b represent the start and end IP addresses of the range, respectively, k represents the name of the property and v the value for the property.

• Get, in the format "? x", where x represents the IP address for which all properties should be fetched.

You may assume the following.

• Each name of a property is a string of at least $1$ and at most $10$ English letters, digits, underscores or dashes.

• Each value of a property is a string of at least $1$ and at most $10$ English letters, digits, underscores or dashes.

• Only an operation which creates property definitions will reference non-existing property names at the time of the operation.

• Each IP address is either a legal IPv4 address or a legal IPv6 address.

Below you can read further explanations of the format of IP addresses.

IPv4

An IPv4 address consists of four parts. Each part is an integer from and including $0$ up to and including $255$ These parts are separated by a single period.

Some examples of valid IPv4 addresses are:

• 10.100.80.13

• 255.255.255.255

• 255.160.134.0

Some examples of invalid IPv4 addresses are:

• 300.1.35.28

• 255.255.255.254.1

• 127,0,0,1

IPv6

An IPv6 address consists of eight parts. Each part is a four digit hexadecimal number. These hexadecimal numbers use the digits from $0$ to $9$ and the letters from $a$ to $f$. The eight parts are separated by single colons. In each part you may omit writing the leading zeros of the number. If two or more adjacent parts contain only the number $0$ they may be omitted and in their place you write two colons. You are only allowed to do this in one place in the IP address.

Some examples of valid IPv6 addresses are:

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

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

• ::1

• abcd:1234::bad:dad

Some examples of invalid IPv6 addresses are:

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

• ffff:1234::f6b90::abcd

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

• 1::3::f

Note that IPv4 addresses may be written as IPv6 addresses. This is done by converting the parts of the IPv4 numbers to hexadecimal and writing the parts with ::ffff: as a prefix. For example, 12.34.56.78 may be written as ::ffff:c22:384e.

Output

For each operation that fetches properties, you should first output one line with the integer $k$, the number of properties of the given IP address. Then $k$ lines should follow, each of them describing a property by name and value, separated by a space. The properties should be output in alphabetical order based on their names. You may assume that your program never needs to output more than $300\, 000$ properties.

Scoring

16
+ user System
= 10.0.0.1 10.0.0.1 user Hannes
= 10.0.0.2 10.0.0.2 user Arnar
+ country IS
+ state -
+ city Reykjavik
= 10.0.0.2 10.0.0.3 city Kopavogur
? 10.0.0.2
= 10.0.0.192 10.0.0.254 country US
= 10.0.0.192 10.0.0.224 state Texas
= 10.0.0.192 10.0.0.196 city Waco
= 10.0.0.194 10.0.0.195 user Fredrik
? 10.0.0.195
- state
? 10.0.0.1
? 10.0.0.3

4
city Kopavogur
country IS
state -
user Arnar
4
city Waco
country US
state Texas
user Fredrik
3
city Reykjavik
country IS
user Hannes
3
city Kopavogur
country IS
user System

6
+ colour red
+ vibe absent
= 10.0.0.92 ::ffff:a00:c0 colour blue
= 1::17 17:: vibe resonant
? 10.0.0.100
? 5::5

2
colour blue
vibe absent
2
colour red
vibe resonant