G. User Registration System
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

"SynergyX", a cutting-edge email service, is launching soon! To expedite the process, we need your help designing a registration system prototype.

The system operates as follows:

  • Add Operation (a username): When a user registers with a username, the system checks if the username exists in the database.
    • If the username is not found, it's added to the database, and the system responds with OK.
    • If the username is found, the system generates a new username by appending numbers (starting from 1) to the original username (e.g., username1, username2, ...). It finds the smallest integer $$$i$$$ such that username$$$i$$$ is not in the database, adds username$$$i$$$ to the database, and returns username$$$i$$$ as the suggested username.
  • Delete Operation (d username): When a user requests to delete their account with username, the system checks if the username exists in the database.
    • If the username is found, it's removed from the database, and the system responds with DELETED.
    • If the username is not found, the system responds with INVALID.
Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), representing the number of operations. The following $$$n$$$ lines each contain an operation in the format: operation username, where operation is either a (add) or d (delete), and username is a non-empty string of length at most 30 consisting of lowercase Latin letters and digits.

Output

For each operation, print the system's response on a separate line. Print OK for successful add operations. Print the suggested username if an add operation encounters a duplicate. Print DELETED for successful delete operations. Print INVALID if a delete operation fails to find the username.

Example
Input
11
a abacaba
a acaba
a abacaba
a acaba
d acaba
a acaba
a a1111111111
d a222222222222222
a a222222222222222
a a222222222222222
a a222222222222222
Output
OK
OK
abacaba1
acaba1
DELETED
OK
OK
INVALID
OK
a2222222222222221
a2222222222222222