EOJ Monthly 2018.10

输入格式

第一行一个整数 $T$，表示有 $T$ ($1\le T\le 333333$) 组测试数据。

每组测试数据有四行。第一行一个整数 $n$ ($2\le n\le 2\cdot {10}^5$)，表示树的节点个数。节点从 $1$ 到 $n$ 编号。

第二行 $n-1$ 个整数 $p_2,p_3,\dots ,p_n$ ($1\le p_i\le i-1$)，分别表示 $2,3,\dots ,n$ 的父亲节点的编号。由于节点 1 是根, 它没有父亲。

第三行是一个长度 $n-1$ 的字符串 $s_2{s}_3\dots s_n$，依次表示节点 $2,3,\dots ,n$ 到父亲节点的边上的字符。$s_i$ 是英文小写字母。

第四行是一个长度为 $n-1$ 的 01 字符串 $a_2{a}_3\dots a_n$，依次表示节点 $2,3,\dots ,n$ 是否是终态。 1 表示是, 0 表示不是。由于字符串的后缀不可能是空串，所以显然节点 1 不是终态。

另外，保证 $T$ 组测试数据中的 $n$ 的和不超过 $2\cdot {10}^6$，且不存在两个节点 $u$, $v$ 满足 $p_u=p_v$ 且 $s_u=s_v$。

本题数据量较大，请注意输入输出上的优化。

输出格式

对于每组测试数据，如果是合法的后缀 Trie，输出一行表示原字符串；如果不是，输出 Illegal。

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

Illegal
banana

提示

下图对应样例 1 中的树。

下图对应样例 2 中的树。