Hidden Hierarchy

You are building the user interface of a simple text based file explorer. One of your tasks is a navigation pane that displays the directory hierarchy. The filesystem consists of directories that hold files and other directories, and those directories again hold files and directories, so the directories form a hierarchical tree. The topmost directory of the hierarchy is the root directory. If directory $d$ directly holds directory $e$, then $d$ is the parent directory of $e$ and $e$ is a subdirectory of $d$. Every file has a size in bytes. The size of a directory is the total size of all files held directly or indirectly inside it.

Every file and every directory except the root has a name, a string that always starts with a lowercase letter and consists of lowercase letters and the "." (dot) character only. Items (files and directories) placed directly inside the same parent directory must have distinct names. Every item is described uniquely by its path, built with the following rules.

• The path of the root directory is a single slash, "/".
• The path of a directory $d$ is obtained by concatenating the directory names top to bottom along the hierarchy from the root directory down to $d$, putting a "/" character in front of each name and one more "/" character at the end.
• The path of a file $f$ is the path of its parent directory followed by the name of $f$.

The hierarchy is displayed by printing the root directory. Printing a directory $d$ means writing one line of the form "$m_d$ $p_d$ $s_d$", where $p_d$ and $s_d$ are the path and the size of $d$, and $m_d$ is its expansion marker, explained below. If $d$ holds other directories, you must choose either to collapse it or to expand it. If you expand $d$, you print all of its subdirectories in lexicographical order by name, using the same rules. If you collapse $d$, you simply ignore its contents.

The expansion marker $m_d$ is a single blank character when $d$ has no subdirectory at all, the "+" (plus) character when you collapse $d$, and the "-" (minus) character when you expand $d$.

Given a list of files and a threshold integer $t$, display the directory hierarchy so that every directory of size at least $t$ is printed and the total number of printed directories is as small as possible. Assume there are no empty directories, so the whole hierarchy follows from the given file paths. The root directory is printed no matter what its size is. A directory of size at least $t$ only has to be printed, it does not have to be expanded.

The first line contains an integer $n$ ($1 \le n \le 1000$), the number of files. Each of the following $n$ lines contains the path $f$ and the size $s$ ($1 \le s \le 10^6$) of a single file, separated by a space. Each path is at most 100 characters long and is a valid file path under the rules above. All paths are different.

The next line contains an integer $t$ ($1 \le t \le 10^9$), the threshold directory size.

Print the display of the hierarchy for the given threshold that uses the smallest number of printed directories, as described above. Each line holds the expansion marker, one space, the path, one space, and the size, in that order.