给定一棵包含 $n$ 个顶点和 $n-1$ 条边的树 $T$。树的每条边都关联有一个小写英文字母 $c_i$。

给定一个由小写英文字母组成的字符串 $s$。你的任务是找到树中的一条简单路径，使得该路径上所有边关联的字母按顺序连接形成的字符串包含 $s$ 作为子序列，或者确定不存在这样的简单路径。

输入格式

第一行包含两个正整数 $n$ 和 $m$ ($2 \le n \le 5 \cdot 10^5$, $1 \le m \le n-1$)，分别表示树的顶点数和字符串 $s$ 的长度。

接下来的 $n-1$ 行，每行包含三个元素 $u_i, v_i, c_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$, $c_i$ 为一个小写英文字母)，表示一条关联字母 $c_i$ 的边 $(u_i, v_i)$。

最后一行包含一个由小写英文字母组成的字符串 $s$ ($|s| = m$)。

输出格式

如果存在满足条件的路径，输出其端点 $a$ 和 $b$。否则，输出 “-1 -1”。如果存在多个可能的答案，输出其中任意一个即可。

样例

样例输入 1

9 3
1 2 a
2 3 b
2 4 a
4 5 b
4 6 c
6 7 d
6 8 a
8 9 b
acb

样例输出 1

8 3