Description

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?

Input Format

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 Format

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

3
Math
Algorithm
Program
2
Picture 2
System 1
3
0
1
3

Math
System
Picture

Hint

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:

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