Cho một chuỗi S gồm các chữ cái thường. Duyệt chuỗi từ trái sang phải, sau mỗi ký tự, hãy in ra ký tự đầu tiên không bị lặp tính đến thời điểm hiện tại. Nếu không có, in ra -1.

Sử dụng queue kết hợp mảng đếm tần số: mỗi khi gặp ký tự c, tăng tần số của c, đẩy c vào queue. Khi cần in, loại bỏ các ký tự ở đầu queue có tần số > 1.

Đầu vào

• Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 10^5) — độ dài chuỗi.
• Dòng thứ hai chứa chuỗi S độ dài N, gồm các chữ cái thường 'a'..'z'.

Đầu ra

In ra N ký tự hoặc -1, mỗi kết quả cách nhau bởi khoảng trắng.

Ví dụ

Input:
7
aabcdeb

Output:
a -1 b b c c d

Giải thích

• Sau 'a': first unique = a
• Sau 'a': không có → -1
• Sau 'b': first unique = b
• Sau 'c': first unique = b (vì 'b' chưa lặp)
• Sau 'd': first unique = c (vì 'b' đã lặp)
• Sau 'e': first unique = c
• Sau 'b': first unique = d