반납된 책 다시 꽂기

문제

사서들은 책을 제자리에 돌려놓지 않는 이용자들 때문에 골머리를 앓는다. 반납된 책은 사서가 시간이 날 때까지 안내 데스크에 모아 두었다가, 서가의 올바른 위치에 다시 꽂는다. 책을 제자리에 꽂는 일은 시간이 매우 많이 걸리므로, 이 작업을 도와주는 프로그램을 작성하자.

이용자가 책을 빌리거나 반납하면 컴퓨터가 그 제목을 기록한다. 사서는 주기적으로 반납된 책의 목록을 요청하여 서가의 올바른 위치에 꽂는다. 책을 꽂기 전에, 반납된 책들은 먼저 저자(author) 순으로, 저자가 같으면 제목(title) 순으로, ASCII 문자 코드를 기준으로 정렬된다. 프로그램은 반납된 책들을 서가에 놓일 순서대로 출력해야 한다. 각 책에 대해, 이미 서가에 꽂혀 있는 책들 중 그 책이 바로 뒤에 놓여야 할 책이 무엇인지(또는 맨 앞에 놓여야 하는지)를 사서에게 알려 주어야 한다.

입력

먼저 도서관이 보유한 모든 책이 한 줄에 하나씩, 정해진 순서 없이 나열된다. 처음에는 모든 책이 서가에 꽂혀 있다. 제목이 같은 책은 없다. 각 줄의 형식은 다음과 같다.

"제목" by "저자"

보유 도서 목록의 끝은 다음 한 단어만 있는 줄로 표시된다.

END

그 뒤에는 책을 빌리고 반납한 기록과, 사서가 책을 다시 꽂아 달라고 요청하는 명령이 이어진다. 각 기록은 한 줄에 하나씩, 다음 형식 중 하나이다.

BORROW "제목"
RETURN "제목"
SHELVE

기록 목록의 끝은 다음 한 단어만 있는 줄로 표시된다.

END

출력

SHELVE 명령이 나올 때마다, 사서를 위한 지시를 한 줄에 하나씩 다음 형식으로 출력한다.

Put "제목1" after "제목2"

또는, 그 책이 전체 장서에서 맨 앞에 놓이는 특수한 경우에는 다음과 같이 출력한다.

Put "제목" first

각 SHELVE에 대한 지시를 모두 출력한 뒤에는, 다음 한 단어만 있는 줄을 출력한다.

END