Longest Prefix Match

An Internet router decides where to send each arriving packet by looking at the packet's destination address. It consults a forwarding table, and that table holds many prefixes.

A prefix is a pair (M, L). M is an address mask, an unsigned 32-bit integer, and L is the number of significant leading bits of M. A destination address D matches the prefix (M, L) when the L most significant bits of D equal the L most significant bits of M. A prefix with L equal to 0 matches every address. The remaining 32 - L low bits of M are ignored.

For every arriving packet the router must find the matching prefix with the largest L. This is called longest prefix match. Given a forwarding table and a list of destination addresses, report the longest prefix match for each address.

The first line contains two integers X and Y separated by a space. X is the number of prefixes in the forwarding table, and Y is the number of packets to forward.

Each of the next X lines describes one prefix as a hexadecimal mask M followed by a decimal length L. Prefixes are numbered from 0 in the order they are given, so the first prefix has id 0 and the second has id 1.

Each of the next Y lines contains the destination address of one packet in hexadecimal.

A hexadecimal number may or may not carry a leading 0x, and its letter digits may be uppercase or lowercase.

• 1 ≤ X ≤ 11,000
• 1 ≤ Y ≤ 1,000,000
• 0 ≤ L ≤ 32
• Masks and addresses are unsigned 32-bit integers.
• The same prefix may appear more than once.

Print Y lines. Line k holds the longest prefix match for the k'th destination address of the input. If at least one prefix matches, print the id of the matching prefix with the largest L. If no prefix matches, print -1.

If several matching prefixes share the largest L, print the smallest id among them.