First Unique IP Hitting the Server

A server receives a sequence of commands in order and must support two operations:

ADD ip: record one visit from ip. FIRST_UNIQUE: among all visits so far, find the IP that appears exactly once and appeared earliest, and return it; if none exists, return an empty string.

Treat IPs as plain strings with no format validation; IPs that differ in case are different IPs. Process all commands in order and output the result of each FIRST_UNIQUE.

输入格式

The first line contains q, the number of commands. Each of the next q lines is ADD ip or FIRST_UNIQUE. 1≤q≤1.5×10^6, and there is at least one FIRST_UNIQUE; the number of distinct IPs is at most 10^6; each ip is a string of length 1..15 consisting of printable ASCII characters (codes 33..126).

输出格式

For each FIRST_UNIQUE, output one line with its result, in order; when the result is an empty string, output an empty line. Every line, including the last, ends with a newline, and the output must match the expected answer byte for byte.

样例 1

输入：

4
ADD 1.1.1.1
ADD 2.2.2.2
ADD 1.1.1.1
FIRST_UNIQUE

输出：

2.2.2.2

样例 2

输入：

7
ADD 1.1.1.1
ADD 2.2.2.2
ADD 1.1.1.1
ADD 3.3.3.3
FIRST_UNIQUE
ADD 2.2.2.2
FIRST_UNIQUE

输出：

2.2.2.2
3.3.3.3

样例 3

输入：

11
FIRST_UNIQUE
ADD 1.1.1.1
FIRST_UNIQUE
ADD 1.1.1.1
FIRST_UNIQUE
ADD x
FIRST_UNIQUE
ADD X
FIRST_UNIQUE
ADD x
FIRST_UNIQUE

输出：

1.1.1.1

x
x
X

样例说明

Example 1: after three ADDs, 1.1.1.1 appears twice and the unique one is 2.2.2.2. Example 2: at the first query the unique IPs are 2.2.2.2 and 3.3.3.3, and the earliest is 2.2.2.2; after another ADD 2.2.2.2 it is no longer unique, so the answer is 3.3.3.3. Example 3: at the first query there are no visits yet, so output an empty line; after ADD 1.1.1.1 the answer is 1.1.1.1, and after its second appearance it is an empty line again; then x becomes the answer, X is a different IP, and after x appears again the answer becomes X.