Problem G
Mutexes

Anna loves coding multithreaded backend services. In such a service, multiple threads may sometimes need to read and write the same data structures in memory. To ensure all threads have a consistent view of a single datastructure, one can use so-called mutexes to protect access to it.

A mutex is an object that threads can acquire and release. When a mutex is acquired, the mutex cannot be acquired again until it is released – even by the same thread! If a thread attempts to acquire a mutex it has already acquired, the thread will deadlock, waiting for itself to release the mutex.

Anna has written a program that consists of a number of functions. Each function consists of a list of commands that execute sequentially when the function is called. The commands are each one of:

• acquire the mutex named $X$

• release the mutex named $X$

• access a data structure protected by the mutex $X$

• call another function

Anna is not sure if she implemented her mutexes correctly, and she wants your help to verify that three properties hold. Assuming a function main is called at the beginning of the program, you should check that:

1. whenever a data structure protected by a mutex $X$ is to be accessed, the mutex $X$ is currently acquired,

2. whenever a mutex is to be acquired, the program has not already acquired it (in order to avoid a deadlock),

3. whenever a mutex is to be released, the program is currently holding it.

Input

The first line of the input contains an integer $N$, the number of functions. This is followed by a description of all the $N$ functions.

The description of a function starts with an integer $M$ ($M \ge 1$) and a string $X$, meaning that there is a function named $X$ with $M$ commands. This is followed by $M$ lines, each containing a command. The commands will be of the form:

• acquire X – the mutex named $X$ is acquired

• release X – the mutex named $X$ is released

• access X – a data structure that must be protected by the mutex $X$ is accessed

• call F – the function called $F$ is called

All functions and mutexes have names between $1-10$ characters in length containing only characters a-z. No two functions will have the same name, and there will always be a function called main.

It is guaranteed that there is no infinite recursion: a function will never call itself, either directly or through a chain of other functions.

Output

If the program is free from errors, output a-ok.

Otherwise, output the first error that occurs during execution. Specifically:

1. if a data structure is accessed without the correct mutex being acquired, output corruption,

2. if a deadlock occurs, output deadlock,

3. if a mutex is released without being acquired, output error.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Let $L$ denote the total number of instructions among all functions, and $K$ the number of mutexes.

3
5 main
acquire mutex
call foo
acquire mutex
call foo
acquire mutex
2 foo
access mutex
release mutex
1 bar
release mutex

a-ok

3
2 f
acquire x
call g
2 g
access x
acquire y
2 main
call f
call g

deadlock

1
3 main
release x
acquire x
access x

error

1
3 main
access x
acquire x
release x

corruption