该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

编程班上的 $n$（ $n$为奇数）名同学是好朋友，编号为1～n。有$n$个位置，初始时在位置$i$的人编号为 $s_i$。

$s_i$将由以下代码生成：

for (int i = 1; i <= n; i++) p[i] = i;
random_shuffle(p + 1, p + 1 + n);
for (int i = 1; i < n; i++)
     s[p[i]] = p[i + 1];
s[p[n]] = p[1];

班内要进行$k$轮换位置游戏。对于每一轮规则如下：

对于每个$i$,如果在位置$i$的⼈编号为$j$，在位置$j$的⼈编号为$t$，则编号为$t$的⼈会换到位置$i$。

例如：4 3 1 5 2->5 1 4 2 3->3 5 2 1 4。

我们已知经过$k$轮换位置游戏之后，在位置$i$的人编号为$p_i$ ，但却忘记了初始时每个人的位置。

请求出初始时在第$i$个位置的人的编号$s_i$ 。

输入格式

第一行一个正整数$T$，代表数据组数。

对于每组数据：

第一行一个正整数$n$ ，其含义见题目描述。

第二行$n$个正整数，其中第$i$个数代表$p_i$。

第三行一个正整数$k$，其含义见题目描述。

输出格式

对于每组数据：

一行，$n$个正整数，其中第$i$个正整数代表$s_i$。

样例

2
5
3 5 2 1 4
2
9
9 6 5 2 1 3 8 4 7
9

4 3 1 5 2
5 4 6 8 3 2 9 7 1

数据范围

本题共有10个测试点。

对于$30\%$的数据，$n ≤ 10, k ≤ 10$

对于$50\%$的数据，$n ≤ 10^3 , k ≤ 10^3$

对于$100\%$的数据，$1 ≤ T ≤ 5, n ≤ 10^3 , k ≤ 10^7$，$n$为奇数，$p_i$为一个排列。