eolymp
bolt
Try our new interface for solving problems
Problems

Rankings

Rankings

Time limit 1 second
Memory limit 64 MiB

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 data

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 (2n500): the number of teams.

  • One line with n integers t_i (1t_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 ti will be distinct.

  • One line with an integer m (0m25 000): the number of pairs whose relative rank order has changed.

  • m lines with two integers a_i and b_i (1a_i < b_in) each: a pair of teams whose relative rank order has changed. Each such pair will be mentioned exactly once.

Output data

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.

Examples

Input example #1
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
Output example #1
5 3 2 4 1
2 3 1
IMPOSSIBLE
Source NWERC-2010