题目描述

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

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

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

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

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

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

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

输入格式

第一行一个整数 $n$。

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

输出格式

如果无解，输出 -1。

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

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

-1

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

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$ 为 \ 或者 /。