Problem F

如果要比较两个字符串的大小，一般方法是先比较第一位的大小，当第一位相同时再比较第二位，当第一位和第二位都相同时再比较第三位$\dots$以此类推，直到两个字符串的第一位不同或者两个字符串完全相同为止。一般认为空串小于任何串。

对于长度为$n$的字符串$S[1,n]$，它有$n$个后缀，第$i$个后缀为$S[i,n]$这个子串。串$S$的后缀数组为数组$sa[1,n]$，其中$sa[i]$表示将这些后缀从小到大排序后，排名第$i$小的后缀是谁。

给定一棵$n$个点的以$1$为根的有根树，每个节点上有一个小写字符$c_i$。定义字符串$str_i$表示从$i$点出发一直沿着父亲往上走到根，这一路中经过的节点上写着的字符从左往右拼起来得到的字符串（包括$i$点和根节点）。

请对于这棵树，求出它的``后缀数组''，即将$str_1,str_2,\dots,str_n$从小到大排序。特别地，如果两个串相等，那么我们认为起点编号较小的串比较小。

第一行包含一个正整数$T(1\leq T\leq 10)$，表示测试数据的组数。

每组测试数据第一行包含两个正整数$n,m(1\leq n\leq 100000,1\leq m\leq 26)$，分别表示点数以及字符范围。

第二行包含一个长度为$n$的字符串$c_1,c_2,\dots,c_n$，依次表示每个节点上的字符。输入数据保证所有$c_i$都在前$m$小的小写字母中完全随机生成。

第三行包含$n-1$个正整数$f_2,f_3,\dots,f_n(1\leq f_i<i)$，其中$f_i$表示$i$点在树上的父亲节点。

对于每组数据，输出一行$n$个整数$res_1,res_2,\dots,res_n$，即排序结果，其中$res_i$表示排序后第$i$小的字符串是$str_{res_i}$。

1
6 3
cabcca
1 2 2 3 5

2 6 3 1 4 5

"字节跳动杯"杭州电子科技大学第二十届程序设计竞赛