Problem11120--洛谷P3850 - [TJOI2007] 书架

11120: 洛谷P3850 - [TJOI2007] 书架

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

Knuth 先生家里有个精致的书架,书架上有 $N$ 本书,如今他想学到更多的知识,于是又买来了 $M$ 本不同的新书。现在他要把新买的书依次插入到书架中,他已经把每本书要插入的位置标记好了,并且相应的将它们放好。由于 Knuth 年龄已大,过几天他已经记不清某些位置上放的到底是什么书了,请问你能帮助他吗?

Input

输入文件的第一行为整数 $N$,接下来 $N$ 行分别是书架上依次放着的 N 本书的书名(书名由不含空格的字符串构成,长度不超过 $10$)。下一行将要输入一个整数 $M$,接下来的 $M$ 行分别为这本书的书名和要插入的位置。下一行将要输入一个整数 $Q$,接下来共有 $Q$ 次询问,每行都是一个整数表示询问的位置。(书架上位置的编号从 $0$ 开始)

Output

输出 $Q$ 行,每行对应着相应查询位置的书名。

Constraints

对于 $30\%$ 的数据,$1 \leqslant N \leqslant 100$, $1 \leqslant M \leqslant 10^3$, $1 \leqslant Q \leqslant 10^3$

对于 $100\%$ 的数据,$1 \leqslant N \leqslant 200$, $1 \leqslant M \leqslant 10^5$, $1 \leqslant Q \leqslant 10^4$

对于 $100\%$ 的数据都符合题目中所描述的限制关系,数据保证每次插入的位置均不超过当时书架上书的数量,而且保证 $Q$ 次查询中的每个位置上一定有书。

Sample 1 Input

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

Sample 1 Output

Math
System
Picture
原来有三本书 Math、Algorithm、Program,后来又买了两本书,分别插入到 $2$ 和 $1$ 的位置,每次插入时其他书都要向后挪一个位置,最后书架上书的序列为:
0  Math
1  System
2  Algorithm
3  Picture
4  Program
$Q$ 次询问依次为 $0$, $1$, $3$ 位置的书,所以答案为:Math、System、Picture

HINT

洛谷P3850.

Source/Category