Longest Prefix Match#3844
In the Internet, a router forwards packets based on their destination address by consulting a forwarding table which specifies for each destination which path (if any) the packet should take next. A destination address is an unsigned -bit integer. The forwarding table contains many distinct prefixes (thousands), and each prefix is a tuple (, ) where is an address mask (an unsigned integer) and is a length specifying the number of relevant bits in the mask. A destination address matches a prefix (, ) if the most significant bits of match the most significant bits of .
Longest Prefix Match: whenever a packet arrives, the router must find the longest prefix from its database that matches the destination address of the packet. You are asked to implement Longest Prefix Match for a router that has to forward a few million packets as quickly as possible.
On the first line there are two integers (x \le 10000) and . denotes the number of prefixes in the router's forwarding table, and gives the number of packets to be forwarded. The next lines describe the prefixes, each line describing one prefix by the hexadecimal mask (it contains no more than bits) followed by the length (0 < len \le 32) in base . Each prefix is identified by number the line it appears on minus one (i.e. the first prefix has id = 0, the second , etc). The next lines give the destination addresses of the packets to be forwarded, with one packet on each line (the addresses are also given in hexadecimal).
Print lines. Line represents the outcome of the longest prefix match algorithm for the 'th address in the input file. The outcome is either the identifier of the longest matching prefix or if no matching prefix was found.
Example 1