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

对于长度为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,...,str_n从小到大排序。特别地，如果两个串相等，那么我们认为起点编号较小的串比较小。

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

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

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

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

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