问题2710--仓鼠与点名

2710: 仓鼠与点名

时间限制: 8 Sec  内存限制: 512 MB
提交: 2  解决: 1
[状态] [讨论版] [提交] [命题人:]
题目描述

小仓鼠是隔壁仓鼠科技大学(Hamster University of Science and Technology)的学生。本学期,小仓鼠修了一门在扇形阶梯教室上的专业课,但是这门课的老师是一名选择困难症患者,每次都不知道点谁回答问题,于是小仓鼠帮老师想到了一种点名方法:

首先将教室里的每个同学编号1~n,然后每位同学拿出一张纸,并在上面写下自己名字的首字母和编号,然后将纸传给坐在他前面的同学;每位同学接到后面同学的纸后,在字母串的最后补上自己名字的首字母然后传给前面的同学,如果前面没有同学,则把它交给老师。如:wk前面是xyxxyx前面是pbpb前面没有同学,那么传到老师手里wk的纸上应该是wxpxyx纸上应该是xp。最后老师每次要点名就随机一个数k,然后叫按纸上字典序为第一关键词、编号为第二关键词排序,综合第k小的同学回答问题(先按字典序排序,如果字典序相同,则编号小的同学在前)

为了简化问题,我们让坐在前面的同学使用更小的编号,即每个同学前面的同学编号小于他自己的,并且让课代表坐在最前面且编号为1
现在给出每个同学名字的首字母以及坐在他前面同学的编号,和q次老师随机出来的数ki,请你回答每次要回答问题的同学的编号是多少?

输入

本题输入含多组数据。第一行有一个数字T1T10 ),表示数据总数

对于每组数据,第一行有三个整数nq1n,q105),表示教室里学生个数和老师随机出的数的个数。

第二行包含一个长度为n的字符串c1,c2,,cnci表示编号为i的同学名字的首字母(小写)

第三行包含n-1个正整数a2,a3,,an(1aii),其中ai表示编号为i的同学坐在他前面同学的编号,1号同学为课代表,他前面没有同学。
接下来q行,每行一个数ki(1kin),表示老师每次随机出来的数。

输出
对于每组数据,输出q行,分别表示每次要回答问题的同学的编号。
样例输入 Copy
1
6 3
cabcca
1 2 2 3 5
2
4
5
样例输出 Copy
6
1
4