Become human

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在 2038 年,仿生人机器人已经可以批量生产,先进的科学技术甚至可以使某些仿生人产生人类的感情,但是仿生人并没有人权。

这里我们模拟一个批量生产的工厂,工厂将仿生人列成了一排,每次生产一个仿生人就将这个仿生人插入到队列的某个位置。工厂有时也会回收某个位置的仿生人,将其从队列中删除。

工厂想知道他将一个仿生人插入到一个位置,或者将某个仿生人删除时,这个仿生人左右相邻的仿生人的编号是多少。

刚开始队列是空的,工厂没有仿生人,保证回收操作时的位置有仿生人。

Input

多组输入:

    第一行输入一个 N,代表接下来输入行 N,代表 N 次操作。(1 <= N <= 100)

         首先输入一个字符 ‘I’ 或 ‘D’,

             如果为 ‘I’,接下来有两个整数 p 和 v,表示插入的位置和仿生人编号。(1 <= v <= 1000)

             如果为 ‘D’,接下来有一个整数 p,表示需要删除的仿生人位置。(1 <= p <= 当前队列的长度,并且队列为空时不会进行回收操作)

Output

 

每次操作输出一行,包含以空格分隔的两个数,分别为当前插入、删除的仿生人左右的仿生人编号,如果左边或右边没有仿生人,那么输出 -1 代替其编号。

Sample Input

1
I 1 68
5
I 1 60
I 2 50
I 3 25
I 4 93
D 1
10
I 1 52
D 1
I 1 19
I 2 32
D 2
D 1
I 1 5
I 1 16
D 2
I 2 7

Sample Output

-1 -1
-1 -1
60 -1
50 -1
25 -1
-1 50
-1 -1
-1 -1
-1 -1
19 -1
19 -1
-1 -1
-1 -1
-1 5
16 -1
16 -1

Hint

Source

【2017级《程序设计基础(B)II》中外期末上机考试】Fish