括号符号包括以下几种：() [] {} <>。一个合法的括号表达式是指由括号符号组成的字符串，满足以下条件：

• 每一个左括号都有一个同类型的右括号与之匹配，且每一个右括号都有对应的左括号；
• 任意两对匹配的括号不会交叉——对于任意两对匹配的括号，它们要么是不相交的，要么其中一对完全包含在另一对内部。

例如，([])<> 是一个合法的括号表达式，而 <{>} 则不是，因为花括号和尖括号发生了交叉。

给定一个包含 $n$ 个顶点的图，其中每条（有向）边都标有一个括号符号。如果一条路径上的边组成的字符串是一个合法的括号表达式，则称该路径是合法的。对于给定的两个顶点 $s$ 和 $t$，请确定从 $s$ 到 $t$ 的最短合法路径的长度。允许路径多次经过同一个顶点。

输入格式

输入的第一行包含四个整数 $n, m, s, t$ ($1 \le n \le 200, 0 \le m \le 2000, 1 \le s, t \le n$)，分别表示顶点数、边数、起点和终点。接下来的 $m$ 行，每行包含两个整数 $x, y$ 和一个括号符号 $b$ ($1 \le x, y \le n$)，描述图中的一条边。注意图中可能存在自环和重边。

输出格式

输出一行，包含一个整数，表示从 $s$ 到 $t$ 的最短合法路径长度。如果不存在这样的路径，输出 $-1$。你可以假设如果路径存在，其长度不会超过 $10^{18}$。

子任务

样例

样例输入 1

4 4 1 4
1 2 (
2 2 [
2 3 ]
3 4 )

样例输出 1

4

样例输入 2

5 4 1 5
1 2 <
2 3 {
3 4 >
4 5 }

样例输出 2

-1