题目描述

现有一个包含 $n$ 块挡板的旧弹球机。

游戏在二维平面内进行，其中每块挡板与坐标轴所夹锐角总为 $45^\circ$，长度为 $1$ 个单位。挡板用其中心坐标 $(x_i,y_i)$ 和字符 / 或 \ 来表示。小球在碰到挡板后，其运动方向将会旋转 $90^\circ$。注意，挡板的两面都可使小球的运动方向发生偏转。

不难发现，当小球处于弹球机中时，它只有两种结局：

• 沿着某一方向一直运动下去而不碰到挡板
• 处于若干个挡板的循环之中

在翻新弹球机的过程中，有四种颜色的染料可供选择。现要将弹球机中的每个挡板进行染色，使得每一个循环内经过每一种颜色的次数相同且为偶数。

请给出一种符合题意的染色方式，或证明这样的染色方式不存在。如果不存在，输出 $-1$。

输入格式

在文件 bieda.in 中读入。

第一行一个正整数 $n$，表示挡板的数量。

接下来的 $n$ 行，每行两个正整数 $x_i,y_i$ 和一个字符 $c_i$（/ 或 \），表示一个挡板。数据保证，挡板的位置不会相互重合。

输出格式

在文件 bieda.out 中输出。

如果不存在符合题意的染色方式，输出 $-1$。

否则输出 $n$ 个整数 $1 \sim 4$，表示 $n$ 个挡板所选择的染料颜色。如果有多种符合题意的方式，输出任意一种。

样例

输入数据1

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

输出数据1

-1

输入数据2

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

输出数据2

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 \

输出数据3

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

提示

数据范围与提示