Hệ thống đăng ký tên

Bối cảnh và bài toán

Một nền tảng học trực tuyến cho phép người dùng chọn tên tài khoản. Máy chủ xử lý yêu cầu theo đúng thứ tự nhận được và phải phản hồi ngay, vì vậy mỗi lần tra cứu hay cập nhật đều cần đủ nhanh khi số người đăng ký lớn.

Với mỗi yêu cầu name:

• nếu name chưa từng được đăng ký, hệ thống đăng ký tên đó và in OK;
• nếu name đã tồn tại, hệ thống nối số dương nhỏ nhất k vào sau name để tạo tên mới chưa dùng, đăng ký tên mới và in tên mới.

Tên trong yêu cầu đầu vào chỉ gồm chữ thường a..z, vì vậy không chứa chữ số. Điều này bảo đảm một tên do hệ thống sinh ra như anna1 sẽ không xuất hiện về sau dưới dạng tên gốc trong đầu vào.

Yêu cầu

Mô phỏng hệ thống và in phản hồi cho từng yêu cầu đăng ký.

Input

• Dòng 1: n.
• n dòng tiếp theo: một tên yêu cầu, độ dài từ 1 đến 32.

Output

Một dòng phản hồi cho mỗi yêu cầu.

Ràng buộc

• 1 <= n <= 10^5

Chấm điểm

Ví dụ 1

Input

4
abacaba
acaba
abacaba
acab

Output

OK
OK
abacaba1
OK

Giải thích. Hai tên đầu chưa tồn tại nên được chấp nhận. Yêu cầu abacaba lần hai bị trùng, vì vậy hệ thống tạo abacaba1. Tên acab vẫn chưa được dùng nên nhận OK.

Ví dụ 2

Input

5
a
a
a
b
a

Output

OK
a1
a2
OK
a3

Giải thích. Sau lần đầu, a đã tồn tại. Ba lần đăng ký trùng tiếp theo nhận lần lượt các hậu tố nhỏ nhất còn trống: a1, a2, a3.

Thông tin bài tập

Nguồn: Phỏng theo Codeforces Beta Round 4 — 4C Registration System.
Tham khảo: https://codeforces.com/problemset/problem/4/C
Ghi chú biên tập: Biên tập lại ngữ cảnh/constraints và chuẩn hóa theo lộ trình FULLHOUSE DEV; giữ bản chất yêu cầu của bài nguồn.