Sadegh and Mahan, influenced by the story of the Grinch and the holiday spirit, have decided to steal Amir's Christmas tree. They drove a van to Tehranpars and snuck into Amir's house. However, upon leaving, they encountered a puzzle that Amir had used to lock his tree. Mahan, who is an Olympiad student, quickly understood the puzzle and explained it to Sadegh as follows:

We have a tree with $n$ vertices, where each edge is labeled with a lowercase English letter. We are also given a secret string $s = s_1 s_2 \dots s_m$. We want to find a path in this tree (without repeating edges) such that by traversing it and concatenating the characters on the edges, we produce the secret string. In other words, we want to find a path with edges $e_{i_1}, e_{i_2}, \dots, e_{i_m}$ such that the string $c_{i_1} c_{i_2} \dots c_{i_m}$ is equal to $s_1 s_2 \dots s_m$, where $c_{i_j}$ is the character written on edge $e_{i_j}$.

You must find this path or declare that no such path with the specified property exists.

Input

The first line of input contains the integer $n$, representing the number of vertices in the tree. In each of the next $n-1$ lines, $u_i$, $v_i$, and $c_i$ are given, representing an edge between vertices $u_i$ and $v_i$ with the character $c_i$. It is guaranteed that $c_i$ is a lowercase English letter. It is also guaranteed that the given edges form a tree. The last line contains the string $s$, which consists only of lowercase English letters.

Output

In the only line of output, print two space-separated integers representing the starting vertex and the ending vertex of the path, respectively. If no such path exists, print "-1 -1".

Constraints

• $2 \le n \le 10^5$
• $1 \le u_i, v_i \le n$
• $1 \le |s| \le n - 1$

Examples

Input 1

4
1 2 a
2 3 b
3 4 c
bc

Output 1

2 4

Input 2

4
1 2 a
2 3 b
3 4 c
ac

Output 2

-1 -1