“机器人的心跳，排列成图，会是什么样子？”

你有一个竞赛编程机器人，它的心跳频率为每分钟 $n$ 次。第 $i$ 次心跳的强度为 $a_i$。其中 $a_1 \sim a_n$ 是 $1 \sim n$ 的一个排列。

令 $A_i$ 为从序列 $a$ 中删除第 $i$ 个元素后得到的序列，即 $A_i = [a_1, \dots, a_{i-1}, a_{i+1}, \dots, a_n]$。

对于一个由不同元素组成的序列 $p$，令 $G(p)$ 为一个具有 $|p|$ 个顶点的无向图，顶点编号为 $1 \sim |p|$。对于每一对正整数 $1 \le i < j \le |p|$，如果对于所有的 $k \in [i, j] \cap \mathbb{Z}$，都有 $p_k \in [\min(p_i, p_j), \max(p_i, p_j)]$，则在 $G(p)$ 中，顶点 $i$ 和 $j$ 之间存在一条边。令 $F(p)$ 为 $G(p)$ 中从顶点 $1$ 到顶点 $|p|$ 的最短路径长度，其中路径长度定义为路径包含的边数。

令 $f(a) = [F(A_1), F(A_2), \dots, F(A_n)]$。

给定一个长度为 $n$ 的序列 $[b_1, \dots, b_n]$，你的任务是找到 $1 \sim n$ 的一个排列 $a$，使得 $f(a) = b$。

保证至少存在一个解。

输入格式

输入包含多个测试用例。 第一行包含一个整数 $T$ ($1 \le T \le 40\,000$)，表示测试用例的数量。 对于每个测试用例： 第一行包含一个整数 $n$ ($4 \le n \le 10^5$)。 下一行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$。 * 保证至少存在一个解。

保证所有测试用例的 $n$ 之和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，输出一行，包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示你找到的排列。 如果存在多个解，你可以输出其中任意一个。

样例

样例输入 1

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

样例输出 1

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