Memory Allocation

Interview

Time limit1sMemory limit512 MB

Summary

Simulate first-fit malloc and free over 100,000 memory cells and print requested variable values in command order.

Level: Medium6 of 10
Topics: Intervals, Simulation, Hash map, Implementation
Solved: No attempts yet

Problem

Write a program that simulates the execution of commands for reserving and freeing memory. The computer's memory is an array of 100 000 consecutive memory locations, numbered in order from address 1 to 100 000. Initially all locations are free. The commands that can appear are:

var=malloc(s); This command finds the first block of s consecutive free memory locations and reserves them. The function returns the address of the first reserved location. If no block of s consecutive free memory locations exists, the function reserves nothing and returns 0.
free(var); This command frees the memory locations assigned to the variable var (by a previous call to the malloc function) and sets the value of the variable var to 0. If the value of the variable var is already 0 before the function is called, the function does nothing.
print(var); This command prints the value of the variable var.

Every command ends with the character “;” (semicolon). Variables are strings made up of exactly 4 lowercase letters of the English alphabet. Every variable is initialized to the value 0 at the start.

Input

The first line contains the integer n (1 ≤ n ≤ 100 000), the number of commands. The j-th of the following n lines contains the j-th command, formatted exactly as in the problem text, with no extra whitespace. The total number of distinct variables is at most 1000. At least one of the commands is a print command. In every malloc command, 100 ≤ s ≤ 100 000.

Output

On the j-th line, print the result of the j-th print command.

Examples2

Example 1

Input

3
mama=malloc(140);
tata=malloc(120);
print(tata);

Expected output

Example 2

Input

5
aabb=malloc(50001);
bbaa=malloc(50000);
print(aabb);
free(aabb);
print(bbaa);

Expected output

1
0