题目

D老师觉得同学们的打字速度太慢了，所以布置了练习打字的作业。

打字作业由$n$个按键组成，每个按键可能是大写字母， Esc ， Enter ， CapsLock ， Backspace ， ShiftDown ， ShiftUp 。其中 ShiftDown 和 ShiftUp 分别表示 Shift 键按下和抬起，其余按键与键盘上的对应按键相同。

下面介绍每个按键的功能：

1.字母按键： 按下会打出对应的字母。

2.Esc: 按下会将输入法内存储的字母清空。

3.Enter: 按下时若输入法内有存储字母，则将输入法内存储的字母全部打出并清空；否则会打出换行符。

4.CapsLock: 按下会切换当前字母大小写模式，初始模式为小写。

5.Backspace: 按下时若输入法内有存储字母，则删除最后一个存储的字符。否则删除最后一个打出的字符（包括换行符）。

6.ShiftDown: 将 Shift 按键状态切换为按下，在 Shift 按键抬起前，打出或存储于输入法内的按键全部变为相反的大小写状态。

7.ShiftUp: 将 Shift 按键状态切换为抬起， Shift 按键初始状态为抬起状态。

8.特殊规则: 若 ShiftDown 与 ShiftUp 按键连续使用（两者中间没有其他按键），则会切换输入法状态。输入法状态有中文/英文两种，且初始处于英文状态。当输入法为中文状态时，按下的所有字母按键将会被存储在输入法内。当输入法从中文切换到英文状态时，存储的所有按键将会被打出并清空。

D老师要求将作业中的$n$个按键依次按下，并将最后打出的所有字符提交。可怜的Mary并不擅长打字，它求你帮忙完成作业。

输入

第一行输入一个整数$n$，表示按键个数。

接下来$n$行，每行给出一个按键。保证给出的按键符合题目规则。保证 $Shift$ 按键为按下状态时不会出现 ShiftDown 按键，保证 $Shift$ 按键为抬起状态时不会出现 ShiftUp 按键。

输出

输出$n$个按键按完后，所有打出的字符。

Samples

输入数据

11
ShiftDown
A
C
ShiftUp
ShiftDown
ShiftUp
T
Esc
Y
A
Enter

输出数据

ACya

数据规模

共有 10 组测试数据

对于第 1 组数据：没有 CapsLock 按键

对于前 2 组数据：没有 ShiftDown 按键

对于前 3 组数据：没有 Backspace 按键

对于前 4 组数据：没有 ShiftUp 按键

对于前 5 组数据：保证不会切换输入法状态

对于前 6 组数据：没有 Esc 按键

对于前 8 组数据：$1\le n\le 5000$

对于所有数据：$1\le n\le 500000$

我自己

要用STL，求代码