컨설팅

Sogang ICPC 팀은 학회원들을 돕기 위해 Sogang Program Consulting Team(이하 SPC Team)을 만들었다. SPC Team은 학회원들과 화목하게 지내게 될 날을 기대하며, 에러가 발생한 코드를 무료로 디버깅해 주는 컨설팅을 바로 시작했다.

어느 날, SPC Team 모두를 당황시킨 코드가 나타났다. 정상적인 코드처럼 보이는데 원하는 데이터를 얻을 수 없었다. 계속해서 디버깅한 끝에 SPC Team은 한 번에 여러 줄의 명령이 실행되고 있었다는 사실을 알아냈다. 다음 예시를 보자.

1: WRITE A TO B
2: WRITE B TO C
3: READ B
4: READ C
5: EXIT

명령어가 순서대로 실행되면 문제가 없는 코드다. 하지만 1행부터 4행까지 동시에 실행되면 문제가 생긴다. 메모리 A에서 메모리 B로 데이터가 옮겨지기 전에 2행이 실행되면, 메모리 C에 어떤 데이터가 들어갈지 알 수 없다. SPC Team은 다음과 같이 코드를 고쳤다.

1: WRITE A TO B
2: WAIT
3: WRITE B TO C
4: WAIT
5: READ B
6: READ C
7: EXIT

명령어 사이에 WAIT를 넣으면 WRITE A TO B와 WRITE B TO C가 동시에 실행되지 않아, 메모리 C의 데이터가 분명해진다. SPC Team은 문제가 생길 수 있는 경우를 세 가지로 나눴다.

• READ와 WRITE
  • WRITE A TO B와 READ B가 동시에 실행되면 메모리 B의 데이터가 확실하지 않으므로, 두 명령어 사이에 WAIT가 있어야 한다.
  • WRITE A TO B와 WRITE B TO C가 동시에 실행되면 메모리 C의 데이터가 확실하지 않으므로, 두 명령어 사이에 WAIT가 있어야 한다.
• WRITE와 WRITE
  • WRITE A TO C와 WRITE B TO C가 동시에 실행되면 메모리 C의 데이터가 확실하지 않으므로, 두 명령어 사이에 WAIT가 있어야 한다.
  • WRITE A TO B와 다른 WRITE A TO B가 동시에 실행되어도 결과에는 문제가 없다. 그래도 프로그램의 안정성을 위해 두 명령어 사이에 WAIT가 있어야 한다.
• 교착 상태
  • WRITE A TO B와 WRITE B TO A가 동시에 실행되면 메모리 A와 메모리 B의 값이 확실하지 않으므로, 두 명령어 사이에 WAIT가 있어야 한다.

학회원들의 컨설팅 문의가 계속 들어오고 있다. 반복되는 작업에 지친 SPC Team은 이런 상황을 스스로 찾아내 컨설팅해 주는 프로그램을 만들고자 한다. 하지만 SPC Team은 너무 바빠서, 유능한 프로그래머인 당신에게 프로그램 제작을 의뢰했다.

최대 $10\ 000$줄의 명령어가 주어지며, WRITE문, READ문, EXIT문으로 구성된다. EXIT문은 마지막에 한 번만 주어진다.

각 명령어는 다음과 같이 정의되며, 메모리 이름은 1자 이상 3자 이하의 알파벳 대문자로 구성된다.

• WRITE A TO B: 메모리 A의 내용을 메모리 B로 옮긴다. 이때 메모리 A는 READ 상태가 된다.
• READ A: 메모리 A의 데이터를 읽는다.
• EXIT: 프로그램을 종료한다.

WRITE A TO A처럼 같은 메모리로 WRITE를 수행하는 경우는 없다.

WAIT를 최소로 사용한 컨설팅 결과를 기존 명령어들의 순서를 유지하여 출력한다.

한 줄에 명령어 하나만 출력한다. 그러한 컨설팅 결과가 여러 개라면 그중 하나를 출력한다.