Manage Books on Shelves

You are given several test cases where in each test case you need to allocate books to their appropriate shelves according to the genre and available capacity. Each shelf is assigned a genre and has a fixed capacity. Books arriving one by one should be placed on the shelf of the corresponding genre if there is space available. If a shelf is full, or if there is no shelf for the book's genre, then that book cannot be added.

If all books in a test case can be placed, output the message All books added. Otherwise, output the titles of the books that could not be placed. Use an extra blank line to separate the outputs of multiple test cases.

The process is described mathematically as follows:

For each test case, given a set of shelf definitions \( S = \{(g_i, c_i)\} \) where \( g_i \) is the genre id and \( c_i \) is the capacity, and a sequence of book entries \( B = \{(g, t)\} \) where \( g \) is the genre id and \( t \) is the title, allocate each book to shelf \( g \) if \( n_g < c_g \), where \( n_g \) is the current number of books in shelf \( g \). Otherwise, record the title \( t \) as not added.

Finally, if no books are left unplaced, print "All books added"; if there are books that could not be added, list their titles in the same order as they appear in the input.

inputFormat

The input consists of several test cases. Each test case is described as follows:

• The first line contains an integer m representing the number of shelves. If m is 0, the input terminates.
• The next m lines each contain two integers: a genre identifier and the shelf capacity.
• The following line contains an integer n representing the number of books to add.
• The next n lines each contain a genre identifier and a book title (a single word) separated by a space.

All input is provided via standard input (stdin).

outputFormat

For each test case, if all books are added successfully, output All books added. Otherwise, output the titles of the books that could not be placed on their corresponding shelves. Separate the outputs of different test cases by an empty line. All output should be sent to standard output (stdout).

## sample

3
1 2
2 3
3 1
5
1 A
2 B
1 C
3 D
1 E
2
1 1
2 2
1
2 W
0

E
All books added

</p>