Memory Allocation Simulator

Time limit1sMemory limit128 MB

Summary
Simulate first-fit memory allocation and freeing over 100,000 memory cells while processing malloc, free, and print commands on named variables.
Level

Medium6 of 10

Topics
Simulation, Implementation, Sorting
Solved
No attempts yet

Problem

Write a program that executes memory allocation commands in order.

The memory consists of 100,000 consecutive cells, addressed from 1 to 100,000. Initially, every cell is free.

Each command is one of the following.

  1. var=malloc(size);
    • Find the earliest starting address of a contiguous free block of length size. If such a block exists, allocate it and store its starting address in var. If no such block exists, store 0. (100 ≤ size ≤ 100,000)
    • If var already stores another address, that old allocation is not freed automatically.
  2. free(var);
    • If var stores the starting address of a block from a previous successful malloc, free that block and store 0 in var. If var is already 0, nothing happens.
  3. print(var);
    • Output the value stored in var.

Every command ends with a semicolon (;). A variable name consists of exactly four lowercase English letters. There are at most 1,000 distinct variables, and every variable is initialized to 0.

Input

The first line contains the number of commands N. (1 ≤ N ≤ 100,000)

Each of the next N lines contains one command, in the order it is executed.

At least one print command is given.

Output

For each print command, output its result on its own line.

Examples3

  1. Example 1

    Input
    3
mama=malloc(140);
tata=malloc(120);
print(tata);
    Expected output
    141

  2. Example 2

    Input
    5
aabb=malloc(50001);
bbaa=malloc(50000);
print(aabb);
free(aabb);
print(bbaa);
    Expected output
    1
0

  3. Example 3

    Input
    5
baka=malloc(214);
baka=malloc(123);
free(baka);
deda=malloc(100);
print(deda);
    Expected output
    215