Tournament Rank Range

Time limit1sMemory limit128 MB

Summary

Given a single-elimination bracket's match winners, determine each queried player's best possible and worst possible final ranking consistent with the known beat relations.

Level: Medium6 of 10
Topics: Tree, DFS, Combinatorics
Solved: No attempts yet

Problem

There are 2^N players in a single-elimination tournament. The players are numbered from 1 to 2^N. In the first round, player 2k-1 plays against player 2k, the loser of each match is eliminated, and the winner advances. Matches continue until only one player remains.

The tournament result can be represented as a full binary tree. Every non-leaf node stores the winner of that match. If player A defeated player B, and player B defeated player C, then A is also considered to have defeated C.

The champion's rank is fixed as rank 1. Other players may be able to claim several different ranks as long as the known win relation is not contradicted. Given the tournament result and several queried players, find the highest and lowest rank each queried player can possibly have.

Input

The first line contains the number of test cases T.

Each test case consists of three lines.

The first line contains N. (1 <= N <= 7)

The second line contains 2^N - 1 integers describing the tournament result. They are listed from the first round to the final round, and within each round from the leftmost match to the rightmost match. Each integer is the winner number of that match.

The third line contains the number of queries M followed by player numbers p_1, p_2, ..., p_M, separated by spaces.

Output

For each queried player p_i, print one line in the following format.

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

Here h is the highest possible rank and l is the lowest possible rank. Print the answers in the same order as the queries. Print one blank line between the outputs of consecutive test cases.

Examples1

Example 1

Input

2
3
1 3 5 8 1 8 1
2 2 5
4
2 3 6 7 9 11 14 15 3 6 9 15 6 9 6
4 1 15 7 6

Expected output

Player 2 can be ranked as high as 2 or as low as 8.
Player 5 can be ranked as high as 3 or as low as 7.

Player 1 can be ranked as high as 4 or as low as 16.
Player 15 can be ranked as high as 3 or as low as 13.
Player 7 can be ranked as high as 2 or as low as 15.
Player 6 can be ranked as high as 1 or as low as 1.