There is no place like 127.0.0.1

Time limit2sMemory limit256 MB

Summary

Replace each IPv4 address in the text with its mapped word from single entries and non-overlapping ranges, leaving unmatched addresses unchanged.

Level: Easy3 of 10
Topics: Binary search, Sorting, Hash map
Solved: No attempts yet

Problem

A friend of yours replaces common English words with IPv4 addresses in his documents. You want to turn those addresses back into the original words. You got hold of his table of words and addresses. Some entries in the table give a range of addresses instead of a single one.

An IPv4 address is a 32 bit unsigned integer, usually written in dot decimal notation: four 8 bit unsigned integers joined by dots, for example 172.30.12.255. When the address is read as an integer, the first number is the most significant byte.

Replace every address the table covers with the word from the table, and leave every other address alone.

Input

The first line contains an integer $T$ ( $1 \le T \le 50$ ), the number of test cases.

Each test case has a map section and a text section.

The map section starts with an integer $M$ ( $1 \le M \le 1000$ ) on its own line, the number of map entries. Each of the next $M$ lines holds one entry: a word followed by one IPv4 address, or a word followed by two IPv4 addresses. In the first form only that single address is replaced with the word. In the second form every address inside the range is replaced with the word. When a range is given, the first address is always smaller than the second one.

The map has no duplicate entries. No word appears twice, no address appears twice, and no two ranges overlap, so at most one entry covers any given address.

The text section starts with an integer $N$ ( $1 \le N \le 1000$ ) on its own line, the number of lines of text. Each of the next $N$ lines holds at most 20 words and IPv4 addresses separated by single spaces. A word contains only letters of the English alphabet. An address contains only digits and dots, every octet is between 0 and 255, and octets are written without leading zeros.

Output

For each test case, process the lines of text in order. Print each line with every address the map covers replaced by its word. Print an address that has no matching word exactly as it appeared, and print words unchanged. Separate the items on a line with single spaces.

Examples6

Example 1

Input

1
3
home 127.0.0.1
smile 255.255.255.0 255.255.255.255
gate 10.0.0.1
4
There is no place like 127.0.0.1
Hannibal at the 10.0.0.1
Let us put a 255.255.255.89 on that face
I am very very 1.2.3.4

Expected output

There is no place like home
Hannibal at the gate
Let us put a smile on that face
I am very very 1.2.3.4

Example 2

Input

1
2
alpha 8.8.8.8
beta 1.0.0.0 1.0.0.255
2
alpha beta gamma
8.8.8.9 1.0.1.0 2.2.2.2

Expected output

alpha beta gamma
8.8.8.9 1.0.1.0 2.2.2.2

Example 3

Input

1
1
mid 192.168.0.10 192.168.0.20
1
192.168.0.9 192.168.0.10 192.168.0.15 192.168.0.20 192.168.0.21

Expected output

192.168.0.9 mid mid mid 192.168.0.21

Example 4

Input

1
2
zero 0.0.0.0
all 0.0.0.1 255.255.255.255
2
0.0.0.0 255.255.255.255
0.0.0.1 128.0.0.0

Expected output

zero all
all all

Example 5

Input

1
4
one 1.1.1.1
two 2.2.2.0 2.2.2.9
three 3.3.3.3
four 4.0.0.0 4.255.255.255
2
one 1.1.1.1 two 2.2.2.5 three 3.3.3.3 four 4.4.4.4 five 5.5.5.5 six 6.6.6.6 seven 7.7.7.7 eight 8.8.8.8 nine 9.9.9.9
2.2.2.10 4.0.0.0 4.255.255.255 3.3.3.4

Expected output

one one two two three three four four five 5.5.5.5 six 6.6.6.6 seven 7.7.7.7 eight 8.8.8.8 nine 9.9.9.9
2.2.2.10 four four 3.3.3.4

Example 6

Input

1
3
low 10.0.0.0 10.0.0.255
high 10.0.1.0 10.0.1.255
point 10.0.2.0
1
10.0.0.255 10.0.1.0 10.0.1.255 10.0.2.0 10.0.2.1

Expected output

low high high point 10.0.2.1