길이가 $n$인 정수 수열 $a_1, a_2, \dots, a_n$이 주어집니다.

이 수열의 가능한 모든 $n$가지 순환 이동(회전)을 고려합시다. 시작 위치 $p$($1 \le p \le n$)에 대해, 대응하는 순환 이동은 다음과 같은 수열입니다:

$$b_1, b_2, \dots, b_n = a_p, a_{p+1}, \dots, a_n, a_1, a_2, \dots, a_{p-1}.$$

이 이동된 수열에 대해, 접두사 최댓값 수열 $c_1, c_2, \dots, c_n$을 다음과 같이 정의합니다:

$$c_i = \max(b_1, b_2, \dots, b_i) \quad \forall i = 1, 2, \dots, n.$$

길이가 같은 두 수열은 일반적인 사전순을 사용하여 비교합니다. 즉, $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$이고 $c_i < d_i$를 만족하는 인덱스 $i$가 존재할 때 그리고 그때에만 $c$가 $d$보다 사전순으로 작습니다.

여러분의 과제는 가능한 $n$가지 순환 이동 중에서 접두사 최댓값 수열이 사전순으로 가장 작아지도록 원래 수열의 순환 이동을 선택하는 것입니다.

입력

첫 번째 줄에는 테스트케이스의 개수를 나타내는 단일 정수 $T$($1 \le T \le 2 \cdot 10^5$)가 주어집니다.

각 테스트케이스는 두 줄로 구성됩니다:

• 첫 번째 줄에는 단일 정수 $n$($1 \le n \le 5 \cdot 10^5$)이 주어집니다.
• 두 번째 줄에는 $n$개의 정수 $a_1, a_2, \dots, a_n$($1 \le a_i \le n$)이 주어집니다.

모든 테스트케이스에 걸친 $n$의 합은 $5 \cdot 10^5$을 초과하지 않음이 보장됩니다.

출력

각 테스트케이스마다 순환 이동 후 사전순으로 가장 작은 접두사 최댓값 수열을 이루는 $n$개의 정수를 한 줄에 출력합니다.

예제

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

1 5 5 5 5
1 3 3 3
1 1 2 2 3
1 1 2 3 3
1 2 2 3 3 4
1 2 2 3 3 4