뮤텍스

Anna는 멀티스레드 백엔드 서비스를 작성하는 것을 좋아한다. 이런 서비스에서는 여러 스레드가 메모리의 같은 자료구조를 읽고 쓸 때가 있다. 자료구조 하나를 모든 스레드가 일관되게 보도록 하려면 뮤텍스를 써서 접근을 보호할 수 있다.

뮤텍스는 스레드가 획득하고 해제할 수 있는 객체이다. 뮤텍스가 획득된 상태에서는 해제되기 전까지 다시 획득할 수 없으며, 같은 스레드라도 마찬가지다. 이미 획득한 뮤텍스를 스레드가 다시 획득하려 하면, 스레드는 자기 자신이 뮤텍스를 해제하기를 기다리며 교착 상태에 빠진다.

Anna는 여러 함수로 이루어진 프로그램을 작성했다. 각 함수는 호출되면 순서대로 실행되는 명령의 목록이다. 명령은 다음 중 하나이다.

• 이름이 $X$인 뮤텍스를 획득한다
• 이름이 $X$인 뮤텍스를 해제한다
• 뮤텍스 $X$로 보호되는 자료구조에 접근한다
• 다른 함수 $F$를 호출한다

Anna는 자신이 구현한 뮤텍스가 올바른지 확신하지 못해서, 다음 세 성질이 성립하는지 검증하려 한다. 프로그램은 main 함수를 호출하면서 시작한다고 가정한다.

• 뮤텍스 $X$로 보호되는 자료구조에 접근할 때, 뮤텍스 $X$가 현재 획득된 상태여야 한다.
• 뮤텍스를 획득할 때, 프로그램이 그 뮤텍스를 이미 획득하고 있지 않아야 한다(교착 상태 방지).
• 뮤텍스를 해제할 때, 프로그램이 그 뮤텍스를 현재 보유하고 있어야 한다.

첫 줄에 함수의 개수 $N$이 주어진다. 이어서 $N$개 함수에 대한 설명이 주어진다.

함수 설명은 정수 $M$과 문자열 $X$로 시작한다. 이는 이름이 $X$이고 명령이 $M$개인 함수가 있다는 뜻이다. 다음 $M$줄에는 명령이 한 줄에 하나씩 주어지며, 명령은 다음 형식 중 하나이다.

• acquire X: 이름이 $X$인 뮤텍스를 획득한다
• release X: 이름이 $X$인 뮤텍스를 해제한다
• access X: 뮤텍스 $X$로 보호되는 자료구조에 접근한다
• call F: 이름이 $F$인 함수를 호출한다

모든 함수 이름과 뮤텍스 이름은 1자 이상 10자 이하이며, 소문자 a-z로만 이루어진다. 같은 이름의 함수는 없으며, main이라는 이름의 함수가 반드시 있다.

무한 재귀는 없다. 함수가 자기 자신을 직접 호출하거나, 다른 함수를 거쳐 간접적으로 호출하는 경우는 없다.

프로그램에 오류가 없으면 a-ok를 출력한다.

오류가 있으면 실행 중 처음 발생한 오류를 출력한다.

• 올바른 뮤텍스를 획득하지 않은 상태에서 자료구조에 접근하면 corruption을 출력한다.
• 교착 상태가 발생하면 deadlock을 출력한다.
• 획득하지 않은 뮤텍스를 해제하면 error를 출력한다.

$L$은 모든 함수의 명령 개수의 합이다.

$L \le 50\,000$