Assign Server Numbers by Type

Each server type is numbered independently; an allocation uses the smallest positive integer not currently in use, and a released number can be reused.

The standard input/output format and supplementary bounds on this site are as defined in this problem statement.

输入格式

The first line contains q (1≤q≤2×10^5), followed by q lines allocate type or deallocate type id. Type names contain no spaces; a released id is guaranteed to be currently allocated.

输出格式

Output the number assigned by each allocate on its own line.

样例 1

输入：

8
allocate db
allocate db
allocate cache
deallocate db 1
allocate db
allocate cache
deallocate cache 1
allocate cache

输出：

1
2
1
1
2
1

样例 2

输入：

4
allocate a
deallocate a 1
allocate a
allocate b

输出：

1
1
1

样例 3

输入：

4
allocate a
allocate b
deallocate b 1
allocate b

输出：

1
1
1