Sadegh 和 Mahan 受《格林奇偷走圣诞节》故事的影响，加上节日氛围的烘托，决定偷走 Amir 的圣诞树。他们开着货车前往 Tehranpars，偷偷溜进了 Amir 的家。但在离开时，他们发现 Amir 用一个谜题锁住了他的圣诞树。Mahan 作为一名奥赛选手，很快就理解了这个谜题，并向 Sadegh 解释道：

我们有一棵包含 $n$ 个顶点的树，每条边上都写有一个小写英文字母。此外，我们还有一个字符串 $s = s_1 s_2 \dots s_m$。我们想要在树中找到一条路径（不重复经过边），使得沿着路径遍历并连接各边上的字符后，生成的字符串恰好等于 $s$。换句话说，我们想要找到一条由边 $e_{i_1}, e_{i_2}, \dots, e_{i_m}$ 组成的路径，使得字符串 $c_{i_1} c_{i_2} \dots c_{i_m}$ 等于 $s$，其中 $c_{i_j}$ 是边 $e_{i_j}$ 上所写的字符。

你需要找到这条路径，或者指出不存在满足该特征的路径。

输入格式

第一行包含一个整数 $n$，表示树的顶点数。在接下来的 $n-1$ 行中，每行依次给出 $u_i$、$v_i$ 和 $c_i$，表示连接顶点 $u_i$ 和 $v_i$ 的边，其上标记的字符为 $c_i$。保证 $c_i$ 为小写英文字母。同时保证给出的边构成一棵树。最后一行包含字符串 $s$，该字符串仅由小写英文字母组成。

输出格式

在唯一的一行输出中，打印两个由空格分隔的整数，分别表示路径的起点和终点。如果不存在这样的路径，则输出 -1 -1。

数据范围

• $2 \le n \le 10^5$
• $1 \le a_i, b_i \le n$
• $1 \le |s| \le n - 1$

样例

样例输入 1

4
1 2 a
2 3 b
3 4 c
bc

样例输出 1

2 4

样例输入 2

4
1 2 a
2 3 b
3 4 c
ac

样例输出 2

-1 -1