Unique User ID Generator

You are given a series of queries to generate unique user IDs for different user types. The system supports three types of users: admin, user, and guest. Each valid user type has an associated prefix: \(A_\) for admin, \(U_\) for user, and \(G_\) for guest.

The task is to implement a user ID generator that, for each query, prints a new identifier for the corresponding user type by appending a sequential number to the prefix. Specifically, if \(c\) denotes the counter for a user type, then the generated ID will be of the form prefix concatenated with the new value \(c+1\), i.e., \(\text{ID} = \text{prefix} + (c+1)\). The counters are initialized to zero. If an invalid user type is encountered, print "Invalid user type" and terminate the program immediately without processing further queries.

Input: The first line contains an integer n representing the number of queries. The next n lines each contain a string representing a user type.

Output: For every valid user type, output the corresponding unique ID on a new line. If an invalid user type is provided, output "Invalid user type" and exit immediately.

inputFormat

The first line of input contains an integer n (\(1 \le n \le 10^5\)) indicating the number of user ID requests. Each of the following n lines contains a string which is one of admin, user, or guest. Any other string should be considered invalid.

outputFormat

For each valid query, output the generated user ID on a separate line according to the corresponding prefix and its sequential order. If an invalid user type is encountered, output "Invalid user type" (without quotes) and terminate the program immediately.

## sample

3
admin
user
guest

A_1
U_1
G_1

</p>