#P3850. [TJOI2007] 书架

    ID: 4998 远端评测题 2000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2007各省省选平衡树枚举,暴力天津

[TJOI2007] 书架

题目描述

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

输入格式

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

输出格式

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

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

提示

原来有三本书 Math、Algorithm、Program,后来又买了两本书,分别插入到 2211 的位置,每次插入时其他书都要向后挪一个位置,最后书架上书的序列为:

0  Math
1  System
2  Algorithm
3  Picture
4  Program

QQ 次询问依次为 00, 11, 33 位置的书,所以答案为:Math、System、Picture

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

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

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