A router's forwarding table lists networks and next hops. For each destination address, print the next hop of the matching route with the longest prefix, or drop if no route matches.
Input
A line with n (1 ≤ n ≤ 50), then n lines network/prefix hop. Then a line with q (1 ≤ q ≤ 50), then q addresses. No two routes have the same network and prefix.
Output
One line per address: the next hop, or drop.
Examples
Example 1 · Input
4 10.0.0.0/8 B 10.1.0.0/16 C 10.1.2.0/24 D 0.0.0.0/0 E 4 10.1.2.7 10.1.9.9 10.200.0.1 8.8.8.8
Expected output
D C B E
Example 2 · Input
2 192.168.0.0/16 X 192.168.1.0/24 Y 2 192.168.1.5 172.16.0.1
Expected output
Y drop
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Store each route as (network number, prefix length, next hop).
Hint 2
An address matches a route when address & mask == network & mask.
Hint 3
Keep the matching route with the largest prefix length; print drop if none matches.
Solution
Show one correct solution (try it yourself first)
def to_number(ip):
n = 0
for part in ip.split("."):
n = n * 256 + int(part)
return n
routes = []
for _ in range(int(input())):
net, hop = input().split()
ip, prefix = net.split("/")
routes.append((to_number(ip), int(prefix), hop))
for _ in range(int(input())):
address = to_number(input().strip())
answer, best = "drop", -1
for net, p, hop in routes:
mask = (0xFFFFFFFF << (32 - p)) & 0xFFFFFFFF
if address & mask == net & mask and p > best:
answer, best = hop, p
print(answer)