C - Rankings

C Rankings

There are n teams (labelled from 1 to n) who take part in a programming competition every year, and at the end they are ranked in order of merit. The rankings for last year are known. This year, the jury wants to make the event less competitive, and decides not to publish such a ranking list (since teams near the bottom might get disheartened). Instead, they will produce a complete list of pairs of teams whose relative rank order has changed from last year to this year. For example, if team 13 placed above team 6 last year, but team 6 placed above team 13 this year, the pair (6, 13) is announced. This would enable teams to track their progress against a particular opposing team, but not give them a clear sense of where they stand overall.

Of course, this isn't going to stop your team from trying to determine the overall ranking list. Given last year's rankings and a complete list of the pairs of teams whose relative rank order has changed, reconstruct as much of this year's standings as possible. It is possible that the jury might have made an error, so if the data given is inconsistent with any possible ranking list for this year, you should also detect this.

Input

On the first line a positive integer: the number of test cases, at most 100. After that per test case:

One line with an integer n (2 ≤ n ≤ 500): the number of teams.
One line with n integers t_i (1 ≤ t_i ≤ n): the rankings for last year, from best team to worst team. t_i represents the team who came in position i (1-indexed) on the ranklist. All the t_i will be distinct.
One line with an integer m (0 ≤ m ≤ 25 000): the number of pairs whose relative rank order has changed.
m lines with two integers a_i and b_i (1 ≤ a_i < b_i ≤ n) each: a pair of teams whose relative rank order has changed. Each such pair will be mentioned exactly once.

Output

Per test case:

One line with n integers: the rankings for this year, from best to worst, where the i-th term (1-indexed) represents the team in position i. If this team cannot be determined with certainty, the integer should be replaced with a `?' character. If the data for a particular test case is inconsistent with any possible ranking list for this year, the line must contain "IMPOSSIBLE" instead.

Sample in- and output

Input	Output
3 5 5 4 3 2 1 2 2 4 3 4 3 2 3 1 0 4 1 2 3 4 3 1 2 3 4 2 3	5 3 2 4 1 2 3 1 IMPOSSIBLE