Parallel Computer Simulator

Time limit1sMemory limit128 MB

Summary

Simulate up to ten concurrent programs on one CPU with FIFO scheduling, quantum preemption, and lock/unlock mutual exclusion, then report prints in execution order.

Level: Medium6 of 10
Topics: Simulation, Queue, Implementation, Array
Solved: No attempts yet

Problem

On a single-processor system, programs that seem to run concurrently only appear to run at the same time. In reality the single CPU switches between programs, executing a few instructions of one program before moving on to the next. Simulate the concurrent execution of up to ten such programs and report the output they produce.

The program currently being executed is said to be running, while every program awaiting execution is ready. A program is a sequence of at most 200 statements, one per line, terminated by an end statement. The available statements are:

Statement type	Syntax
Assignment	`<variable> = <constant>`
Output	`print <variable>`
Begin mutual exclusion	`lock`
End mutual exclusion	`unlock`
Stop execution	`end`

A <variable> is a single lowercase letter and a <constant> is an unsigned decimal integer less than 1000. The system has only 26 variables, shared by every program, so an assignment made by one program changes the value another program may later print. All variables start at zero.

Each statement takes an integral number of time units to execute. A running program keeps executing instructions for a stretch of time called its quantum. When the quantum expires, another ready program is chosen to run; any instruction already in progress when the quantum expires is allowed to finish.

Programs wait in a first-in-first-out ready queue. Its initial order matches the order of the programs in the input. This order can change because of lock and unlock.

lock and unlock give a program mutually exclusive access to the variables it manipulates. They always appear in pairs that bracket one or more statements; a lock always precedes its matching unlock, and the pairs are never nested. Once a program executes a lock, no other program can execute a lock until the holder runs its matching unlock. If a running program tries to execute a lock while one is already held, it is placed at the tail of the blocked queue and forfeits the rest of its current quantum. When an unlock is executed, the program at the head of the blocked queue (if any) is moved to the head of the ready queue; the first statement it runs will be the lock that previously failed. Enforcing mutual exclusion is up to the programs themselves: a program that never locks can freely change any variable regardless of the discipline the others follow.

Input

The first line contains seven integers separated by spaces: the number of programs that follow, then the execution time (in time units) of each of the five statement types in the order listed above (assignment, print, lock, unlock, end), and finally the number of time units in one quantum.

The rest of the input is the programs themselves, each well-formed according to the rules above. Every statement starts in the first column of its line; any blanks inside a statement are to be ignored. Each program has an identification number equal to its position in the input (the first program is 1, the second is 2, and so on).

Output

Print the output produced by the print statements in the order they are executed during the simulation. For each executed print, output the program's identification number, a colon, a space, and the value of the requested variable. The output of different print statements appears on separate lines.

Examples4

Example 1

Input

3 1 1 1 1 1 1
a = 4
print a
lock
b = 9
print b
unlock
print b
end
a = 3
print a
lock
b = 8
print b
unlock
print b
end
b = 5
a = 17
print a
print b
lock
b = 21
print b
unlock
print b
end

Expected output

Example 2

Input

1 1 1 1 1 1 100
a = 5
print a
b = 10
print b
end

Expected output

1: 5
1: 10

Example 3

Input

2 1 1 1 1 1 1
a = 1
print a
end
a = 2
print a
end

Expected output

1: 2
2: 2

Example 4

Input

2 1 1 1 1 1 1
lock
x = 5
print x
unlock
end
lock
x = 9
print x
unlock
end

Expected output

1: 5
2: 9