Silco 目前正试图制造一支由微光（shimmer）控制的机器人大军来统治世界。

目前，他计划制造 $N$ 个机器人，编号为 $1$ 到 $N$。他有 $K$ 台机器可以用来制造这些机器人，编号为 $1$ 到 $K$。

他还有一份包含 $M$ 个步骤的清单，用于制造他所有的机器人。每个步骤都指出，某个特定的机器人需要指定的机器执行类型为 A 或 B 的操作。每个机器人对每台机器最多只需要进行一次操作。

为了制造一个机器人，Silco 必须按照步骤描述，在指定的机器上执行每一项操作。然而，B 类型的操作会使机器受到微光的污染，而如果机器已被污染，则无法在其上执行 A 类型的操作。因此，在一台机器上，所有 A 类型的操作必须在所有 B 类型的操作之前执行。Silco 不能在机器人只制造了一部分时就切换去制造另一个机器人，即 Silco 必须在完全制造完一个机器人后，才能开始制造下一个机器人。

Silco 想要知道他是否能够制造出所有的机器人。请帮他找到一个制造机器人的顺序，使得所有的机器人都能被成功制造！

输入格式

第一行包含三个空格分隔的整数 $N, M, K$（$1 \le N, M, K \le 5 \cdot 10^5$），分别表示机器人的数量、总步骤数和机器的数量。

接下来 $M$ 行，描述制造所有机器人所需的步骤。其中第 $i$ 行包含两个整数和一个字符（均用空格分隔）$n_i$（$1 \le n_i \le N$）、$k_i$（$1 \le k_i \le K$）和 $c_i$（$c_i \in \{\text{A}, \text{B}\}$）。这表示编号为 $n_i$ 的机器人需要使用编号为 $k_i$ 的机器，且操作类型为 $c_i$。

输出格式

如果可以制造出所有的机器人，输出单行 $N$ 个空格分隔的整数 $p_1, p_2, \dots, p_N$，其中 $p_i$ 是按顺序制造的第 $i$ 个机器人。如果有多个可行的顺序，输出其中任意一个即可。

如果无法制造出所有的机器人，输出单行，包含数字 $-1$。

样例

输入样例 1

3 5 5
1 2 B
1 3 A
2 1 B
2 2 A
3 5 A

输出样例 1

2 1 3

输入样例 2

3 5 3
1 1 A
1 2 B
2 1 B
2 2 A
3 3 A

输出样例 2

-1