Cho một mảng A gồm n số nguyên dương a₁, a₂, …, aₙ.

Với mỗi phần tử aᵢ, hãy tìm phần tử bên phải aⱼ gần aᵢ nhất sao cho tần số của aⱼ lớn hơn tần số của aᵢ.

Tần số của một giá trị x là số lần xuất hiện của x trong mảng A.

Yêu cầu: Với mỗi phần tử aᵢ, hãy tìm giá trị aⱼ gần nhất bên phải thỏa mãn:

j > i và tần số(aⱼ) > tần số(aᵢ).

Nếu không tồn tại phần tử nào thỏa mãn thì ghi -1.

INPUT

• Dòng đầu tiên chứa số nguyên dương t (1 ≤ t ≤ 100) là số test;
• Với mỗi test, dòng tiếp theo chứa số nguyên dương N;
• Dòng tiếp theo chứa N số nguyên dương a₁, a₂, …, aₙ.

OUTPUT

Gồm t dòng, mỗi dòng ghi N số nguyên, số thứ i là giá trị aⱼ thỏa mãn điều kiện đề bài.

Nếu không tồn tại aⱼ thỏa mãn thì ghi -1.

Ràng buộc

• 20% số test tương ứng với 20% số điểm có t ≤ 100, N ≤ 100, 1 ≤ aᵢ ≤ 100;
• 80% số test tương ứng với 80% số điểm có t ≤ 100, N ≤ 10⁵, 1 ≤ aᵢ ≤ 10⁵.

Ví dụ

Sample Input

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

Sample Output

-1 2 2 1 1 -1 2 1 -1 -1
-1 -1 -1 -1 -1
2 2 -1 -1 -1 -1

Giải thích

Với test 1:

A = 1 3 7 2 5 1 4 2 1 5

Tần số của từng phần tử tương ứng là:

3 1 1 2 2 3 1 2 3 2

Ví dụ:

• Với a₁ = 1, tần số là 3. Không có phần tử bên phải nào có tần số lớn hơn 3 nên kết quả là -1;
• Với a₂ = 3, tần số là 1. Phần tử bên phải gần nhất có tần số lớn hơn 1 là a₄ = 2, nên kết quả là 2;
• Với a₃ = 7, tần số là 1. Phần tử bên phải gần nhất có tần số lớn hơn 1 là a₄ = 2, nên kết quả là 2.