Problem E
Directory Management

Tired of using existing badly written operating systems, Hieu decided to write a new one. Of course, his new operating system will be awesome, bug-free, fast and easy to use. He has finished most of the work, and now he is asking you to do one last task: Implement a directory manager. Initially, Hieu’s computer directory is empty. The current directory is the root directory.

The directory manager keeps the directory in a rooted-tree structure. In each directory, the children are sorted in lexicographic order.

He can do one of the following actions:

• MKDIR $s$: create a child directory named $s$ inside the current directory where $s$ is a string.

  • If the current directory already contains a child directory named $s$, print “ERR” and do nothing.

  • Otherwise, print “OK”

• RM $s$: remove a child directory named $s$ inside the current directory where $s$ is a string.

  • If there is no child directory named $s$, print “ERR”. Otherwise, print “OK”.

• CD $s$: change the current directory to a child directory named $s$ where $s$ is a string.

  • If $s$ is equal to the string “..” and the current directory is the root directory, print “ERR” and do nothing.

  • If $s$ is equal to the string “..” and the current directory is not the root directory, then change the current directory to the parent directory and print “OK”.

  • If there is no child directory named $s$, print “ERR” and do nothing.

  • If there is a child directory named $s$ then change the current directory to $s$ and print “OK”.

• SZ: Print the total size of the current directory.

  • The size of a directory is defined as $1$ + the total size of its children.

• LS: list the child directories of the current directory in lexicographic order.

  • If there is no child directory, print “EMPTY”.

  • If the number of child directories is between $1$ and $10$ inclusive, print all its children.

  • If there are more than $10$ child directories in the current directory, print the first $5$ children, followed by a line containing only “...”, followed by the last $5$ children.

  For example, if you are at “root” directory of the example in Figure $1$, LS would print out the following:

  dira
  dirb
  dirc

• TREE: list all the directories inside the current directory, in pre-order traversal where the children are visited in lexicographic order.

  • If there is no child directory, print “EMPTY” (do not print the current directory).

  • If the number of directories (counting all descendants, and including the current directory) is between $1$ and $10$ inclusive, print all the directories using pre-order traversal.

  • If there are more than $10$ directories (counting all descendants, and including the current directory) inside the current directory, instead of printing all the lines, only print the first $5$ lines, followed by a line containing “...”, followed by the last $5$ lines.

  For example, if you are at “root” directory of the example in Figure $1$, TREE would print out the following:

  root
  dira
  a
  b
  c
  dirb
  x
  dirc
  y

• UNDO: undo the effect of the last command that satisfy the following three conditions. If there is no command to UNDO the print “ERR”. Otherwise, print “OK”.

  • The command has to be one of the following commands: MKDIR or RM or CD.

  • The command did not result in printing “ERR”.

  • The command has not yet been undone by any UNDO command.

Given a list of commands, your task is to execute those commands and print the output.

Input

The input consists of several datasets. The first line of the input contains the number of datasets which is a positive integer and is not greater than $20$. The following lines describe the datasets.

Each dataset is described by the following lines:

• The first line contains only one integer $Q$ – the number of commands.

• Each of the next $Q$ lines contains one of the commands described above.

  • For commands MKDIR, RM, CD: $s$ can contain only lowercase characters (except for the case “CD ..”) and the length of $s$ does not exceed $4$.

Each dataset has the following constraints:

• The total number of commands does not exceed $10^5$.

• The total number of MKDIR and RM commands does not exceed $5\, 000$.

Output

The output for each dataset should be separated by an empty line. For each command, you need to print out exactly like the above explanations. The judgement of this problem is case-sensitive.

1
22
MKDIR dira
CD dirb
CD dira
MKDIR a
MKDIR b
MKDIR c
CD ..
MKDIR dirb
CD dirb
MKDIR x
CD ..
MKDIR dirc
CD dirc
MKDIR y
CD ..
SZ
LS
TREE
RM dira
TREE
UNDO
TREE

OK
ERR
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
9
dira
dirb
dirc
root
dira
a
b
c
dirb
x
dirc
y
OK
root
dirb
x
dirc
y
OK
root
dira
a
b
c
dirb
x
dirc
y