Mocha và chuyến đi bộ đường dài

Thành phố có $n+1$ ngôi làng và $2n-1$ con đường một chiều. Có hai loại đường:

• $n-1$ con đường nối làng $i$ tới làng $i+1$, với mọi $1\le i\le n-1$.
• $n$ con đường được mô tả bởi dãy $a_1,a_2,\dots ,a_n$: nếu $a_i=0$ thì có đường một chiều từ làng $i$ tới làng $n+1$; nếu $a_i=1$ thì có đường một chiều từ làng $n+1$ tới làng $i$.

Hãy tìm một hành trình đi qua mỗi ngôi làng đúng một lần. Hành trình có thể bắt đầu và kết thúc ở làng bất kỳ, nhưng mỗi bước phải đi theo chiều của một con đường đã cho. Nếu không tồn tại hành trình như vậy, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu. Mỗi bộ dữ liệu gồm hai dòng.
• Dòng đầu của mỗi bộ chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ (mỗi $a_i$ bằng $0$ hoặc $1$).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng gồm $n+1$ số nguyên, trong đó số thứ $i$ là ngôi làng thứ $i$ trong hành trình. Nếu không tồn tại hành trình, in ra $-1$.

Nếu có nhiều đáp án đúng, in ra bất kỳ đáp án nào.

Ràng buộc

• $1\le t\le 20$
• $1\le n\le {10}^4$
• $0\le a_i\le 1$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^4$.

Ví dụ