你负责研究一个新物种，并希望确保你收集的数据是正确的。

这里有若干个生物。对于每一个生物，你都知道它们的眼睛颜色。眼睛颜色由前 20 个小写英文字母（从 ‘a’ 到 ‘t’）中的一个表示。

你认为存在一个控制眼睛颜色的基因。你的假设是每个生物都有两个等位基因（Alleles）。等位基因由一个小写英文字母表示。生物最终的眼睛颜色是这两个等位基因中按字母顺序排列在前的那一个。

此外，你已经确定了每个生物的两个亲本。部分亲本信息可能缺失；要么两个亲本的信息都已知，要么都未知。生物从每个亲本那里继承一个等位基因；四种组合中的任何一种都是可能的。例如，一个拥有等位基因 ‘ak’（因此眼睛颜色为 ‘a’）的亲本，与另一个拥有等位基因 ‘em’（眼睛颜色为 ‘e’）的亲本，可能生出一个拥有等位基因 ‘ae’（眼睛颜色为 ‘a’）、‘am’（眼睛颜色为 ‘a’）、‘ek’（眼睛颜色为 ‘e’）或 ‘km’（眼睛颜色为 ‘k’）的孩子。

给定生物的数量、亲本信息以及每个生物的眼睛颜色，请确定这些信息是否与你的假设一致。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 20$)，表示研究中的生物数量。生物编号为 $1$ 到 $n$。

接下来的 $n$ 行，每行包含两个整数 $p_1, p_2$（满足 $1 \le p_1, p_2 \le n, p_1 \neq p_2$ 或 $p_1 = p_2 = 0$）以及一个字符 $c$ ($c \in \{‘a’, \dots, ‘t’\}$)，其中 $p_1$ 和 $p_2$ 代表该生物的亲本（如果亲本未知则均为 0），$c$ 是该生物的眼睛颜色。注意，要么两个亲本都已知，要么都未知，且两个亲本的编号都小于该生物的编号；没有任何生物可以是其自身的祖先或后代。

输出格式

如果信息一致，请按行输出每个生物的等位基因，每行一对，中间无空格；否则输出 $-1$。如果存在多种可能的解，请仅输出按字母顺序排列最靠前的那一个（例如，第一个生物的等位基因对按字母顺序最靠前，然后是第二个，以此类推）。

样例

样例输入 1

3
0 0 a
0 0 b
1 2 c

样例输出 1

ac
bc
cc

样例输入 2

3
0 0 c
0 0 c
2 1 a

样例输出 2

-1