Returning Books

Interview

Time limit1sMemory limit128 MB

Summary

Track which books are on the shelves and which sit at the desk, then on each SHELVE command report where each returned book belongs by comparing author and title in ASCII order.

Level: Medium6 of 10
Topics: Sorting, Array, Implementation, Binary search
Solved: No attempts yet

Problem

Librarians have trouble with borrowers who don't return books to their proper places. Returned books are kept at the main desk until a librarian is free to put them back in the right places on the shelves. Because reshelving each book in the correct spot can be very time-consuming, write a program to help.

When a borrower borrows or returns a book, the computer records its title. Periodically the librarian asks the program for the list of returned books so they can be placed in their correct positions on the shelves. Before they are shelved, the returned books are sorted first by author and then by title, using the ASCII character set. Your program should output the returned books in the same order in which they should appear on the shelves. For each book, tell the librarian which already-shelved book the returned book should be placed immediately after (or that it should be placed first).

Input

First, the library's stock is listed, one book per line, in no particular order. Initially they are all on the shelves. No two books have the same title. Each line has the format:

"title" by "author"

The end of the stock listing is marked by a line containing only:

END

Following the stock list is a series of records of books borrowed and returned, together with requests from the librarian for help reshelving. Each record appears on a single line, in one of the following formats:

BORROW "title"
RETURN "title"
SHELVE

The list of records is terminated by a line containing only:

END

Output

Each time a SHELVE command appears, output a series of instructions for the librarian, one per line, in the format:

Put "title1" after "title2"

or, for the special case of the book being the first in the collection:

Put "title" first

After the instructions for each SHELVE, output a line containing only:

END

Examples2

Example 1

Input

"The Canterbury tales" by "Chaucer, G."
"Algorithms" by "Sedgwick, R."
"The C programming language" by "Kernighan, R"
END
BORROW "The Canterbury tales"
BORROW "Algorithms"
BORROW "The C programming language"
RETURN "Algorithms"
RETURN "The C programming language"
SHELVE
RETURN "The Canterbury tales"
SHELVE
END

Expected output

Put "The C programming language" first
Put "Algorithms" after "The C programming language"
END
Put "The Canterbury tales" first
END

Example 2

Input

"Cherry" by "Smith, J."
"Apple" by "Smith, J."
"Banana" by "Smith, J."
"Zebra" by "Adams, K."
END
BORROW "Apple"
BORROW "Banana"
BORROW "Cherry"
BORROW "Zebra"
RETURN "Cherry"
RETURN "Apple"
RETURN "Banana"
RETURN "Zebra"
SHELVE
END

Expected output

Put "Zebra" first
Put "Apple" after "Zebra"
Put "Banana" after "Apple"
Put "Cherry" after "Banana"
END