녹아웃 토너먼트

$2^n$명의 선수가 참가하는 녹아웃(단판 탈락) 토너먼트가 있다. 한 번이라도 지면 그 선수는 탈락하고, 각 경기의 승자끼리 다시 맞붙어 마지막 한 명이 남을 때까지 진행한다.

선수에게 $1, 2, 3, \ldots, 2^n$의 번호를 매기고, 1라운드에서는 $k = 1, 2, \ldots, 2^{n-1}$에 대해 선수 $2k-1$과 $2k$가 맞붙는다고 하자. 그러면 토너먼트 전체 결과를 완전 이진 트리로 나타낼 수 있으며, 각 내부 노드에는 그 경기의 승자를 적는다.

예를 들어 $n = 3$인 토너먼트를 보자. 1라운드에서 $(1,2)$의 승자는 1, $(3,4)$의 승자는 3, $(5,6)$의 승자는 5, $(7,8)$의 승자는 8이다. 2라운드에서 $(1,3)$의 승자는 1, $(5,8)$의 승자는 8이다. 결승 $(1,8)$의 승자는 1이므로 우승자는 선수 1이다.

토너먼트가 끝난 뒤, 기자들이 경기 결과로 정해지는 선수들의 상대적 순위를 두고 논쟁을 벌였다. 여기서 '이김'은 추이적이라고 가정한다. 즉 선수 A가 선수 B를 이기고 B가 C를 이겼다면 A도 C를 이긴 것으로 본다. 이렇게 하면 누가 최고의 선수인지는 의심의 여지가 없다.

문제는, 한 선수가 토너먼트 결과를 근거로 주장할 수 있는 가장 높은 순위와 가질 수 있는 가장 낮은(나쁜) 순위가 무엇인가 하는 것이다. 예를 들어 위 토너먼트에서 선수 2는 결국 우승한 선수에게만 졌으므로 자신이 전체 2위라고 주장할 수 있지만, 실제로는 최하위(8위)일 수도 있다. 선수 5는 (2위가 될 수도 있는 선수에게 졌으므로) 최고 3위까지 주장할 수 있지만, 1라운드에서 한 명을 이겼으므로 아무리 낮아도 7위보다 나쁠 수는 없다.

토너먼트 결과와 관심 있는 선수들의 목록이 주어질 때, 각 선수가 가질 수 있는 가장 높은 순위와 가장 낮은 순위를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 세 줄로 구성된다.

첫째 줄에는 양의 정수 $n$ ($n < 8$)이 주어진다. 이는 토너먼트에 $2^n$명의 선수가 있고 $1$번부터 $2^n$번까지 위에서 설명한 방식대로 짝지어짐을 뜻한다. $n = 0$은 입력의 끝을 의미한다.

둘째 줄에는 1라운드부터 순서대로 각 라운드의 경기 결과가 (한 라운드 안에서는 왼쪽에서 오른쪽 순서로) 주어진다. 즉 1라운드의 승자 $2^{n-1}$개, 2라운드의 승자 $2^{n-2}$개, $\ldots$, 마지막 라운드의 승자 1개 순으로 총 $2^n - 1$개의 승자 번호가 나열된다. 예를 들어 앞의 $n = 3$ 토너먼트는 다음과 같이 주어진다.

1 3 5 8 1 8 1

셋째 줄에는 양의 정수 $m$과 이어서 $m$개의 정수 $k_1, \ldots, k_m$이 주어진다. 각 $k_i$는 이 토너먼트에 참가한 선수의 번호이다.

각 $k_i$에 대해 다음 형식으로 한 줄씩 출력한다.

Player ki can be ranked as high as h or as low as l.

여기서 ki는 선수 번호, h는 그 선수가 주장할 수 있는 가장 높은 순위, l은 가질 수 있는 가장 낮은 순위이며, 각각 알맞은 수로 바꿔 출력한다. 출력 줄들은 입력에서 $k_i$가 주어진 순서와 같은 순서로 나타나야 한다. 서로 다른 테스트 케이스의 출력 사이에는 빈 줄 하나를 넣어 구분한다.