#715 Yet Another Hamiltonian Path Problem

Statement

Statement language

There is a directed graph with $N$ vertices numbered $1,2,\cdots,N$ .

Each vertex $i$ has a value $A_i$ . Directed edges exist according to the following rules.

If $A_i=0$ , then for every $j<i$ , there is a directed edge from vertex $i$ to vertex $j$ .

Find a Hamiltonian path, a path that visits every vertex exactly once, in this graph.

For every two consecutive vertices of the path, there must be an edge in the direction of travel. The path does not need to return to its starting vertex.

For example, if $N=4$ and $(A_1,A_2,A_3,A_4)=(1,0,1,0)$ , then is a Hamiltonian path. It visits each vertex exactly once, and all three directed edges , , and exist.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, if no Hamiltonian path exists, print -1 on one line.

Otherwise, let $p_1,p_2,\cdots,p_N$ be the vertices of a Hamiltonian path in visiting order. Print on one line, separated by spaces. The sequence must be a permutation of , and for every , there must be a directed edge from vertex to vertex .

Constraints

$1\le T\le 250\,000$ .
$2\le N\le 500\,000$ .
$A_{i}$ ().

Subtasks

#	Score	Constraints
1	9	$N=2$ .
2	22	$A_i\ge A_{i+1}$ (). In other words, all s come before all s. Arrays consisting entirely of s or entirely of s are also included.

Samples

Input

Output

In the first test case, the path $2\to1$ is a Hamiltonian path.

In the second test case, no Hamiltonian path exists.

The remaining output lines are also examples of Hamiltonian paths satisfying the required conditions.