Roy 和 Biv 拥有一个包含 $n$ 个节点的无向图，节点编号为 $1..n$。图中的每条边都有一个权重和一种颜色。权重为正整数。边的颜色恰好有三种：红色（Red）、绿色（Green）和蓝色（Blue）。图中可能存在重边，也可能存在自环。

对于一个固定的正整数 $k$，考虑以下任务：Roy 和 Biv 想要选择恰好 $k$ 条边，并删去其余所有边。他们希望在仅保留所选的 $k$ 条边时，两人都能看到整个图是连通的。

然而，这里有一个限制：Roy 看不到红色边，而 Biv 看不到蓝色边。因此，他们必须选择这样一些边，使得蓝色边和绿色边足以连通所有节点，同时红色边和绿色边也足以连通所有节点。对于从 $1$ 到总边数的所有 $k$ 值，求出能使 Roy 和 Biv 都认为图是连通的 $k$ 条边的最小权重之和。

输入格式

输入包含单个测试用例。注意，你的程序可能会在不同的输入上多次运行。每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 100$)，其中 $n$ 是图中节点的数量，$m$ 是边的数量。

接下来的 $m$ 行，每行包含两个整数 $a, b$ ($1 \le a, b \le n$)，一个整数 $w$ ($1 \le w \le 1\,000$) 和一个字符 $c$ ($c \in \{R, G, B\}$)，表示连接节点 $a$ 和 $b$ 的一条权重为 $w$、颜色为 $c$ 的边（$R$ 代表红色，$G$ 代表绿色，$B$ 代表蓝色）。

输出格式

输出 $m$ 行，每行依次表示 $k = 1..m$ 时的结果。如果对于某个 $k$ 值，Roy 和 Biv 无法同时认为图是连通的，则输出 $-1$。否则，输出能使 Roy 和 Biv 都认为图是连通的 $k$ 条边的最小权重之和。

样例

输入 1

5 8
1 5 1 R
2 1 2 R
5 4 5 R
4 5 3 G
1 3 3 G
4 3 5 G
5 4 1 B
1 2 2 B

输出 1

-1
-1
-1
-1
15
14
17
22