최장 접두사 일치

인터넷 라우터는 패킷이 도착하면 목적지 주소를 보고 그 패킷을 다음에 어디로 보낼지 정한다. 이때 참고하는 자료가 전달 표이고, 전달 표에는 접두사가 여러 개 들어 있다.

접두사는 (M, L) 쌍이다. M은 32비트 부호 없는 정수인 주소 마스크이고, L은 M에서 의미가 있는 상위 비트의 개수다. 목적지 주소 D의 상위 L비트가 M의 상위 L비트와 같으면 D는 접두사 (M, L)과 일치한다. L이 0이면 그 접두사는 모든 주소와 일치한다. M의 나머지 하위 32 - L비트는 무시한다.

라우터는 패킷이 도착할 때마다 목적지 주소와 일치하는 접두사 중에서 L이 가장 큰 것을 찾아야 한다. 이것을 최장 접두사 일치라고 한다. 전달 표와 목적지 주소 목록이 주어지면 각 주소의 최장 접두사 일치 결과를 구하라.

첫째 줄에 정수 X와 Y가 공백으로 구분되어 주어진다. X는 전달 표에 있는 접두사의 개수이고, Y는 전달할 패킷의 개수다.

다음 X개 줄에는 접두사가 한 줄에 하나씩 주어진다. 각 줄은 16진수 마스크 M과 10진수 길이 L로 이루어진다. 접두사의 번호는 주어진 순서대로 0부터 매긴다. 첫 번째 접두사의 번호는 0, 두 번째 접두사의 번호는 1이다.

다음 Y개 줄에는 전달할 패킷의 목적지 주소가 16진수로 한 줄에 하나씩 주어진다.

16진수는 앞에 0x를 붙일 수도 있고 붙이지 않을 수도 있으며, 알파벳 자리는 대문자와 소문자를 모두 쓸 수 있다.

• 1 ≤ X ≤ 11,000
• 1 ≤ Y ≤ 1,000,000
• 0 ≤ L ≤ 32
• 마스크와 주소는 32비트 부호 없는 정수다.
• 같은 접두사가 두 번 이상 나올 수 있다.

Y개의 줄을 출력한다. k번째 줄에는 입력의 k번째 목적지 주소에 대한 최장 접두사 일치 결과를 출력한다. 일치하는 접두사가 있으면 그중 L이 가장 큰 접두사의 번호를 출력하고, 일치하는 접두사가 하나도 없으면 -1을 출력한다.

L이 가장 큰 접두사가 여러 개이면 그중 번호가 가장 작은 것을 출력한다.