The Smallest Open Interval

题目描述

Given a set $S$ of points on the $x$ -axis. For any point $p$ , you are suppose to find the smallest open interval that contains $p$, provided that the two ends of the interval must be in $S$.

输入格式

Each input file contains one test case. Each case consists of several lines of commands, where each command is given in the format:

cmd num

where $cmd$ is either $I$ for "insert", or $Q$ for "query", or $E$ for "end"; and $num$ is an integer coordinate of a point on the $x$-axis. It is guaranteed that num is in the range$[-10^9, 10^9]$ . The input is ended by $E$. It is guaranteed that there are no more than $10^5$ distinct points in $S$, and so is the number of queries. The total number of commands (E not included) is no more than $3×10^5$.

输出格式

For each $I$ case, insert $num$ into $S$. For each $Q$ case, output the smallest open interval that contains num in the format $(S_1,S_2)$, where both $S_1\ and\ S_2$ must be in $S$. On the other hand, if num is no larger than the smallest point in $S$, s1 shall be replaced by $-inf$, representing negative infinity; or if num is no smaller than the largest point in $S$, $s2$ shall be replaced by $+inf$ , representing positive infinity. It is guaranteed that there must be at least $1$ point in $S$ before the first query.

样例 #1

样例输入 #1

I 100
Q 100
I 0
I 33
I -200
Q 25
Q 33
Q -200
Q 200
E

样例输出 #1

(-inf, +inf)
(0, 33)
(0, 100)
(-inf, 0)
(100, +inf)