Dana jest permutacja $p$ liczb $1\sim n$.

Należy skonstruować ciąg $a$ długości $n$, który spełnia następujące warunki:

• Każdy element ciągu $a$ jest dodatnią liczbą całkowitą nie większą niż $n$.
• Nie istnieje uporządkowana para liczb całkowitych $(l,r)$, dla której $1 \le l \le r \le n$ oraz $\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_i$.

Albo należy stwierdzić, że rozwiązanie nie istnieje.

Permutacją liczb $1\sim n$ nazywamy ciąg, w którym każda dodatnia liczba całkowita nie większa niż $n$ występuje dokładnie raz.

Wejście

Zadanie zawiera wiele przypadków testowych.

Pierwszy wiersz zawiera liczbę całkowitą $T$, oznaczającą liczbę przypadków testowych.

Następnie podane są kolejno przypadki testowe. Dla każdego z nich:

• Pierwszy wiersz zawiera liczbę całkowitą $n$.
• Drugi wiersz zawiera $n$ liczb całkowitych opisujących daną permutację $p$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz:

• Jeżeli istnieje ciąg $a$ spełniający warunki, wypisz $n$ liczb całkowitych oddzielonych spacjami, opisujących skonstruowany ciąg $a$.
• Jeżeli taki ciąg $a$ nie istnieje, wypisz $-1$.

Każdy wynik spełniający wymagania zostanie zaakceptowany.

Przykład

Wejście 1

4
3
3 2 1
2
1 2
5
4 2 1 5 3
7
5 7 3 1 2 4 6

Wyjście 1

1 3 3
-1
5 3 2 1 1
2 3 5 4 6 3 1

Uwagi

W przypadku testowym $1$ zarówno $\{1,3,3\}$, jak i $\{1,1,3\}$ są ciągami $a$ spełniającymi warunki.

Dla przypadku testowego $2$ można udowodnić, że ciąg $a$ spełniający warunki nie istnieje.

W przypadku testowym $3$, oprócz $\{5,3,2,1,1 \}$, warunki spełniają także ciągi $a$ takie jak $\{3,4,5,3,2 \}$, $\{1,4,5,3,4 \}$ i $\{5,3,3,4,5\}$.

Ograniczenia

Niech $\sum n$ oznacza sumę wartości $n$ w pojedynczym pliku testowym.

Dla wszystkich danych zachodzi $1 \le T \le 5000$, $2 \le n \le 10^6$, $\sum n \le 10^6$; gwarantuje się, że $p$ jest permutacją liczb $1\sim n$.