IP routing table with longest prefix match

Build the forwarding table of an IPv4 router. Routes are CIDR prefixes mapped to a next-hop name. When a packet arrives, the router must send it to the next hop of the most specific route that covers its destination address (longest prefix match).

Implement a class RoutingTable:

• add_route(cidr: str, next_hop: str) -> None adds a route such as "10.1.0.0/16". If the same prefix already exists, replace its next hop. Bits after the prefix length are ignored, so "10.1.2.77/24" is the same prefix as "10.1.2.0/24".
• remove_route(cidr: str) -> bool removes a route. Return True if it existed, otherwise False. Removing a prefix must not affect longer prefixes inside it.
• lookup(ip: str) -> str | None returns the next hop of the longest prefix that contains ip, or None if no route matches. A /0 route (0.0.0.0/0) is the default route and matches every address.

Constraints:

• Addresses are dotted-quad IPv4 strings. Prefix lengths are 0 to 32. Raise ValueError for malformed input.
• Up to 10^5 routes and 10^6 lookups. A lookup must not scan every route.

Example:

add_route("172.16.0.0/12", "core")
add_route("172.20.0.0/16", "east")
add_route("172.20.5.0/24", "rack-5")
lookup("172.20.5.40")   -> "rack-5"
lookup("172.20.9.1")    -> "east"
lookup("172.31.0.1")    -> "core"
lookup("8.8.8.8")       -> None
add_route("0.0.0.0/0", "upstream")
lookup("8.8.8.8")       -> "upstream"
remove_route("172.20.0.0/16") -> True
lookup("172.20.9.1")    -> "core"
lookup("172.20.5.40")   -> "rack-5"

Reconstructed from the reported question; details may differ from what interviewers ask.