题目描述

译自 COCI 2021/2022 Contest #5 T3「Fliper」

Mirko 和 Slavko 发现了一个旧弹球机。

弹球游戏在一个二维平面上进行，在平面上有 $n$ 块挡板，它们均与坐标轴呈 $45^\circ$ 角摆放，长度为 $1$ 单位长度。挡板由其中点坐标 $(x_i, y_i)$ 和一个字符 \ 或 / 描述，挡板两两不同。球总沿平行于坐标轴的方向运动。如果一个球撞上了挡板，球的运动方向会顺/逆时针旋转 $90^\circ$。注意挡板的两面均可以使球的运动方向旋转。

为了翻新弹球机，Mirko 和 Slavko 决定使用 $4$ 种不同的颜色来为挡板上漆。

他们发现，球的最终结局只有两个：被困在一个循环内，或者直接无限的向某个方向运动。

他们决定，对于每一个可能的循环，一遍循环内球经过每一种颜色的次数需要相同且是偶数。

请你构造一组给挡板上漆的方案满足上述条件，或者证明不存在这种方案，如果不存在，输出 -1。

---

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 $x_i, y_i$，一个字符 $c_i$。

---

输出格式

如果无解，输出 -1。

否则，输出一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 块挡板的颜色，如果有多组方案，你可以只输出一种。

---

样例 1

输入

4
1 1 \
3 1 /
3 2 \
1 2 /

输出

-1

不难发现这的确是一个循环，但是我们要使得每一种颜色出现偶数次，所以无解。

---

样例 2

输入

9
1 2 \
1 3 /
2 1 \
2 2 \
2 3 \
3 1 /
3 2 \
4 2 /
4 3 \

输出

1 3 2 4 1 3 2 4 1

仅有一个循环，下图是样例所构造的方案。

---

样例 3

输入

12
1 2 \
1 3 /
2 1 \
2 2 \
2 3 \
2 4 /
3 1 /
3 2 \
3 3 \
3 4 \
4 2 /
4 3 \

输出

1 3 2 4 2 4 1 3 1 3 2 4

---

数据范围与提示

对于全部数据，保证
$1 \le n \le 5 \times 10^5$，
$|x_i|, |y_i| \le 10^9$，
$c_i$ 为 \ 或 /。

子任务

编号	特殊限制	分值
1	$n \le 40$	20
2	最多存在一个循环
3		70

---