神奇的传送门

题目描述

$\text{Zeta}$ 和他的朋友们正在探索一组神奇的传送门。经过不懈的探索，他们发现，每穿过一次传送门，自己都会被传送到某个传送门的门前（可能是同一扇门）。

如果有 $n$ 个人分别站在 $n$ 扇门前，每当他们同时穿过自己面前的门时，他们就会分别被传送到不同门前，即每扇门前有且仅有一人。

传送门之间有一定的传递关系，我们可以用一个数列 $\lbrace a_n\rbrace$ 来表示某一次的传递关系，$a_i$ 表示 $i$ 号门传送到 $a_i$ 号门，显然，每一次传送中传送门的传递关系一般是不同的。

现在有 $n$ 个人分别站在 $n$ 个传送门前，人和传送门的编号均为 $1,2,...,n$ ，起初他们站在自己对应的传送门前，他们会共同穿过 $k+1$ 次自己面前的传送门，已知他们的最终位置，以及从倒数第 $2$ 次传送到第 $1$ 次传送中传送门的传递关系，请你推断出最后一次传送中传送门的传递关系。

一句话概括：对于集合 $A=\lbrace 1,2,...,n \rbrace$ 存在 $n!$ 种双射（一一映射） $f:A\rightarrow A$ , 现给出其中 $k+1$ 种映射 $f,f_k,f_{k-1},...,f_2,f_1$ , 求映射 $f_{k+1}$ 使得 $f_{k+1}\circ f_k\circ...\circ f_2\circ f_1 = f$ .（其中 $\circ$ 为映射的复合，例如 $(f_1\circ f_2)(x)=f_1[f_2(x)]$ 。）

输入

第一行 $1$ 个整数 $t$ 表示数据组数。$(1\le t \le 50)$

对于每组数据输入 $k+2$ 行：

• 第一行 $2$ 个整数 $n,k$ 含义如题所示。（$1\le n \le 2\times 10^3,1\le k \le 100$）

• 第二行 $n$ 个整数，第 $i$ 个数表示第 $i$ 号人最终站在的传送门的编号。

• 接下来 $k$ 行，每行 $n$ 个整数，从后往前地给出传送门的传递关系，即第 $m$ 行第 $i$ 个数 $a_i$ 表示在倒数第 $m$ 次传送中，$i$号门传送到 $a_i$ 号门。

输出

输出共 $t$ 行。

对于每组数据，输出一行 $n$ 个整数，第 $i$ 个数 $a_i$ 表示在最后一次传送中 $i$ 号门传送到 $a_i$ 号门。

输入样例

1
5 3
2 1 3 4 5
1 5 3 2 4
4 1 3 2 5
5 1 2 4 3

输出样例

3 1 5 2 4

样例解释

起初，$1,2,3,4,5$ 号人分别在 $1,2,3,4,5$ 号门前。

然后，经过输入样例最后一行 5 1 2 4 3 的传送，$1,2,3,4,5$ 号人分别在 $5,1,2,4,3$ 号门前。

然后，经过 4 1 3 2 5 的传送，处在 $1$ 号门前的 $2$ 号人被传送到 $4$ 号门前，以此类推，$1,2,3,4,5$ 号人分别在 $5,4,1,2,3$ 号门前

然后，经过 1 5 3 2 4 的传送，$1,2,3,4,5$ 号人分别在 $4,2,1,5,3$ 号门前

最后，经过输出样例 3 1 5 2 4 的传送，处在 $4$ 号门的 $1$ 号人被传送到 $2$ 号门前，以此类推，$1,2,3,4,5$ 号人分别在 $2,1,3,4,5$ 号门前，符合输入样例第三行。

Author:$\zeta$