18 人解决，35 人已尝试。
22 份提交通过，共有 202 份提交。
6.3 EMB 奖励。
3644. 后缀 Trie
单点时限: 3.0 sec
内存限制: 512 MB
Trie 是一种常见的数据结构。不知道 Trie 为何物的，请自行网搜。
若将一个长度为 $n$ 的字符串的所有后缀（总共 $n$ 个）插入一个 Trie 中，则称该 Trie 为字符串的后缀 Trie。
现以有根树的形式给出一个后缀 Trie，试问该树是否为一合法的后缀 Trie。如果是，求出原字符串。
输入格式
第一行一个整数 $T$，表示有 $T$ ($1 \le T \le 333~333$) 组测试数据。
每组测试数据有四行。第一行一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)，表示树的节点个数。节点从 $1$ 到 $n$ 编号。
第二行 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$ ($1 \le p_i \le i - 1$)，分别表示 $2,3,\ldots,n$ 的父亲节点的编号。由于节点 1 是根, 它没有父亲。
第三行是一个长度 $n-1$ 的字符串 $s_2s_3 \ldots s_n$，依次表示节点 $2,3,\ldots,n$ 到父亲节点的边上的字符。$s_i$ 是英文小写字母。
第四行是一个长度为 $n-1$ 的 01 字符串 $a_2a_3 \ldots a_n$，依次表示节点 $2,3,\ldots,n$ 是否是终态。 1 表示是, 0 表示不是。由于字符串的后缀不可能是空串，所以显然节点 1 不是终态。
另外，保证 $T$ 组测试数据中的 $n$ 的和不超过 $2 \cdot 10^6$，且不存在两个节点 $u$, $v$ 满足 $p_u = p_v$ 且 $s_u = s_v$。
本题数据量较大，请注意输入输出上的优化。
输出格式
对于每组测试数据，如果是合法的后缀 Trie，输出一行表示原字符串；如果不是，输出 Illegal。
样例
Input
2 11 1 1 1 2 2 4 6 6 6 7 taioenadnn 0111011111 16 1 1 1 2 3 4 5 6 7 8 9 10 11 12 15 abnnaaannnaaana 100001100001101
Output
Illegal banana
提示
下图对应样例 1 中的树。
下图对应样例 2 中的树。
