6894: BZOJ2894：世界线

由于春希对于第二世代操作的不熟练，所以刚使用完invasion process便掉落到了世界线之外，错综复杂的平行世界信息涌入到春希的意识中。春希明白了事件的真相。 在一个冬马与雪菜同时存在的世界里，傲娇的冬马最终还是博得了春希的内心。然而看着好友雪菜的消瘦，内心愧疚的冬马启动了第二世代操作，想找到一个雪菜最终成功的世界，却发现哪里都没有。绝望的冬马决定耗尽自己全部的第二世代操作点数，自创一个没有自己只有雪菜与春希的世界。 虽然这个世界一开始效果很好，春希与雪菜很快的被命运撮合在了一起，然而没有了冬马的雪菜，如没有了大海的沙滩，失去了傍依。 虽然世界里没有冬马的存在，但是由于冬马创造时的疏忽，这个世界里的雪菜依然存在着因独占春希而产生的对冬马的愧疚感，这种愧疚感折磨着雪菜，最终雪菜选择了自毁忘记春希。 看着这一切的春希深知不管是三个人一起的快乐，还是两个人独处的甜蜜，都无法消除冬马与雪菜内心的自责，无论如何修改世界，三人都只会更加痛苦，于是春希使用了自己剩余的全部操作点数，念出了key world:WhiteAlbum2，开始了initialization process. 在initialization process中，春希需要整理世界线，才能回归原本的世界。 世界线是一棵根节点为1的树，每个节点为1个字符。规定树上的子串为从某个节点（不一定是1号节点）出发往其子节点走所形成的字符串。每一个子串相当于一个平行世界，要想重构世界，就需要知道两个信息： 1.    不同子串的个数 2.    将不同的子串排序后，字典序第k-1小的子串。 如图所示为一个世界线的样例，从4->5的子串为bb,1->5的为abb  

输入格式

第一行两个整数n，q表示节点个数以及询问个数 第二行n个字符，表示编号为i的字符是什么。 接下来n-1行表示一棵树。 接下来q行，每行一个整数k

输出格式

第一行为不同支付串个数。 接下来q行为q个询问的答案(注意输出的是第k-1小的子串，如果K=1请直接换行)，如果不存在（不包括k=1）输出-1.

样例输入

8 1
abcbbaca
1 2
2 3
1 4
4 5
4 6
4 7
1 8 
5

样例输出

12
aba
【数据规模和约定】
12%：n<=10
另有48%为一条链;
100%: n<=250000,q<=50000.	

提示

没有写明提示

题目来源

没有写明来源