思路：用链表维护的话单词修改寻址 $O(n+m)$，修改 $O(1)$ 。由于询问放在一起，所以 $O(n+m)$ 全部打好答案然后每次 $O(1)$ 输出答案。

$m$ 次寻址每次 $O(n+m)$ ，总 $O(m^2+mn)$无法接受，考虑优化。

取一个定值 $317$ ,约等于 $O(\sqrt{m+n})$。

维护第 $i\times317$ 个书在链表中的位置。修改总复杂度降至 $O(m\sqrt{m+n})$ 。

记录

代码（马蜂清奇见谅）：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<set>
using namespace std;
#define rei register int
#define il inline
il const void readln(int &I){
	I=0;char C=getchar();
	while(!isdigit(C))C=getchar();
	while( isdigit(C))I=I*10+C-'0',C=getchar();
}
const int maxn=100205;
const int siz=317;
const int inf=0x7fffffff;

int pos[siz+10],n,m,q;//pos i refers to the position of the (i*siz)-th book

//lianbiao
int size;
struct node{string name;int pre,suf;}a[maxn];
void getsuf(int &it){it=a[it].suf;}
void getpre(int &it){it=a[it].pre;}
int findpos(int x){
	int cur=pos[x/siz],cnt=x%siz;
	if(cnt==0)cur=pos[x/siz-1],cnt+=siz;
	while(cnt--){getsuf(cur);}return cur;
}
void ins(string sx,int u){
	int usuf=findpos(u),upre=a[usuf].pre;
	a[++size]={sx,upre,usuf},a[upre].suf=a[usuf].pre=size;
	for(rei i=u/siz+1;pos[i];i++)getpre(pos[i]);
	if(size%siz==0)pos[size/siz]=a[maxn-1].pre;
}
string si,ans[maxn];int xi,ccnt;
int main(){
	a[0]={"",-inf,maxn-1},a[maxn-1]={"",0,inf},readln(n);//[bg,ed)
	for(rei i=1;i<=n;i++){cin>>si,ins(si,i);}
	readln(m);while(m--)cin>>si,readln(xi),ins(si,xi+1);
	for(rei cur=a[0].suf;cur!=maxn-1;getsuf(cur))ans[++ccnt]=a[cur].name;
	readln(m);while(m--)cin>>xi,printf("%s\n",ans[xi+1].c_str());
}