每年有 $n$ 支队伍（编号为 $1$ 到 $n$）参加一项程序设计竞赛，在比赛结束时，他们会按照成绩进行排名。去年的排名是已知的。今年，评委会希望减弱比赛的竞争性，决定不公布这样的排名表（因为排名靠后的队伍可能会感到沮丧）。相反，他们将公布一份完整的队伍对列表，这些队伍对在去年到今年的相对排名顺序发生了变化。例如，如果去年 13 号队伍排在 6 号队伍之前，而今年 6 号队伍排在 13 号队伍之前，则会公布队伍对 $(6, 13)$。这将使各队伍能够追踪自己与特定对手的相对进展，但不会让他们对自己的整体位置有清晰的认识。

当然，这并不能阻止你的队伍尝试确定整体排名表。给定去年的排名以及相对排名顺序发生变化的完整队伍对列表，请尽可能多地重建今年的排名。评委会可能会犯错，因此如果给定的数据与今年任何可能的排名表都不一致，你也应该检测到这一点。

输入格式

第一行包含一个正整数：测试用例的数量，最多为 $100$。对于每个测试用例：

• 一行包含一个整数 $n$ ($2 \le n \le 500$)：队伍的数量。
• 一行包含 $n$ 个整数 $t_i$ ($1 \le t_i \le n$)：去年的排名，从最好的队伍到最差的队伍。$t_i$ 表示在排名表中名列第 $i$ 位（从 1 开始变址）的队伍。所有的 $t_i$ 都是互不相同的。
• 一行包含一个整数 $m$ ($0 \le m \le 25\,000$)：相对排名顺序发生变化的队伍对数量。
• $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i < b_i \le n$)：一对相对排名顺序发生变化的队伍。每个这样的队伍对将恰好出现一次。

输出格式

每个测试用例：

• 一行包含 $n$ 个整数：今年的排名，从最好的队伍到最差的队伍，其中第 $i$ 项（从 1 开始变址）表示名列第 $i$ 位的队伍。如果无法确定该位置的队伍，则应将该整数替换为字符 ?。如果某个特定测试用例的数据与今年任何可能的排名表都不一致，则该行必须包含 IMPOSSIBLE。

样例

输入样例 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

输出样例 1

5 3 2 4 1
2 3 1
IMPOSSIBLE