E. Safe Memory Management
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have probably heard of the Rust programming language. Perhaps you even know that it guarantees safe memory management thanks to its built-in system of static reference checking. Recently, this language has become widely popular across the visible universe.

During a journey to a star system where a fashion exhibition will take place, the Lorenzo spaceship experienced a malfunction. Due to incorrect warp jump parameter settings, the ship ended up in a quantum turbulence and found itself in the pirate system PRS-1. Unfortunately, the ship was captured by the pirates, and during the negotiations, Lorenzo heard the phrase "Please, use Rust. Use it blazingly fast" several times.

As it turned out, the pirates were obsessed with this language. Furthermore, they were only interested in safe memory management, which involved only memory allocation and deallocation operations. The pirates had absolutely no interest in other features of this remarkable language.

For memory allocation, the pirates use the following construction:

let X = new();

Here and below, "X" denotes the name of a variable consisting only of lowercase Latin letters.

For explicit memory deallocation, the pirates use the following construction:

drop(X);

The language automatically deallocates memory when a variable goes out of scope. To specify the beginning and end of the scope, the symbols "{" and "}" are used, respectively:

{
  let X = new();
}

In case of going out of scope, the compiler adds memory deallocation constructions for variables not yet deallocated in this scope in reverse declaration order, for example:

{
  let a = new();
  let b = new();
  let c = new();
  let d = new();
  drop(c);
}

Will be transformed by the compiler into:

let a = new();
let b = new();
let c = new();
let d = new();
drop(c);
drop(d); // <-
drop(b); // <-
drop(a); // <-

As ransom for the ship, the pirates offered Lorenzo to improve the provided Rust code. Since the pirates only use explicit memory management and do not use automatic deallocation (scopes), they ask you to rewrite their code in a way that minimizes the number of explicit memory deallocation constructions, while not changing the order of memory allocation and deallocation.

Lorenzo still has a chance to make it to the exhibition, but he has absolutely no knowledge of programming, so he asks you to solve this problem.

Input

The first line contains a single integer $$$n$$$ — the number of lines in the pirates' code.

The next $$$n$$$ lines contain the pirates' code. Each line has one of two formats:

  • "let X = new();" — memory allocation for a variable named 'X'.
  • "drop(X);" — memory deallocation for a variable named 'X'.

It is guaranteed that all created variables have unique names consisting only of lowercase Latin letters, with a length not exceeding $$$16$$$ characters. It is also guaranteed that each memory allocation is followed by a single memory deallocation (memory allocation always precedes deallocation).

$$$$$$2 \le n \le 1000$$$$$$

Output

Output the transformed pirates' code containing the minimum number of explicit memory deallocation constructions. If there are multiple possible answers, any one containing the minimum number of scopes is allowed. Consider the entire code to already be within a certain scope.

Each line should have one of the four formats:

  • "let X = new();" — memory allocation for a variable named 'X'.
  • "drop(X);" — memory deallocation for a variable named 'X'.
  • "{" — start of a scope.
  • "}" — end of a scope.

You may also add any number of spaces at the beginning of each line (but not exceeding $$$4\,000$$$).

Examples
Input
6
let aba = new();
let caba = new();
let daba = new();
drop(aba);
drop(daba);
drop(caba);
Output
let aba = new();
let caba = new();
let daba = new();
drop(aba);
Input
8
let a = new();
let b = new();
drop(b);
let c = new();
drop(c);
drop(a);
let e = new();
drop(e);
Output
{
  let a = new();
  {
    let b = new();
  }
  let c = new();
}
let e = new();