P3850 [TJOI2007] Bookshelf

Mr. Knuth has a delicate bookshelf with $N$ books on it. He has bought $M$ different new books to learn more. He will insert the new books into the shelf one by one; he has already marked the position for each book and placed them accordingly. As Knuth is elderly, after a few days he can no longer remember which book is at certain positions. Can you help him?

The first line contains the integer $N$. The next $N$ lines are the titles of the $N$ books currently on the shelf in order (each title is a string without spaces, with length at most $10$). The next line contains the integer $M$. The following $M$ lines each contain the title of a book and the position where it should be inserted. The next line contains the integer $Q$. Then there are $Q$ queries; each line contains an integer denoting a position to query. (Positions on the shelf are numbered from $0$.)

Output $Q$ lines. Each line contains the title of the book at the corresponding queried position.

Originally there are three books: Math, Algorithm, Program. Later he buys two more books and inserts them at positions $2$ and $1$. Each time a book is inserted, other books shift one position to the right. The final sequence on the shelf is: ```plain 0 Math 1 System 2 Algorithm 3 Picture 4 Program ``` The $Q$ queries ask for positions $0$, $1$, $3$, so the answers are: Math, System, Picture. Constraints: - For $30\%$ of the testdata, $1 \leqslant N \leqslant 100$, $1 \leqslant M \leqslant 10^3$, $1 \leqslant Q \leqslant 10^3$. - For $100\%$ of the testdata, $1 \leqslant N \leqslant 200$, $1 \leqslant M \leqslant 10^5$, $1 \leqslant Q \leqslant 10^4$. - For $100\%$ of the testdata, all constraints described in the statement hold: each insertion position never exceeds the current number of books on the shelf, and every queried position always has a book. Translated by ChatGPT 5