Mirko 和 Slavko 偶然发现了一台旧弹球机。游戏由一个小金属球组成，它在机器内部移动，撞击并从一些障碍物上反弹。

游戏在一个平面上进行，平面上有 $n$ 个障碍物。障碍物由相对于坐标轴倾斜 $45^\circ$ 的单位长度线段表示。障碍物由其中心点 $(x_i, y_i)$ 和一个字符（'/' 或 '\'，表示障碍物的方向）唯一确定。平面上还有一个始终沿平行于坐标轴的四个方向之一移动的球。如果球撞击到障碍物，其运动方向会改变 $90^\circ$，球继续移动。注意，障碍物是双面的，这意味着球可以从障碍物的两侧反弹。

Mirko 和 Slavko 决定用一层新漆来修复这台弹球机。他们手头有四个装有四种不同颜色的油漆桶。他们想给每个障碍物涂上这四种颜色中的一种。

Mirko：“你知道吗，我在想。球的路径只有两种可能性。” Slavko：“你是什么意思？” Mirko：“嗯，要么球会陷入一个循环，周期性地重复相同的反弹序列，要么在某个时刻它会飞向无穷远处。” Slavko：“嗯，你说得对。那么也许我们可以尝试给障碍物上色，使得对于每个循环，每种颜色在循环中出现的次数相等，且这个次数是偶数。例如，如果某个循环由 24 次反弹组成，我们应该让每种颜色出现 6 次，而 6 是一个偶数。” Mirko：“那如果没有这样的上色方案呢？” Slavko：“你知道该怎么做，直接输出 -1。”

请帮助 Mirko 和 Slavko 确定一种满足所需条件的障碍物上色方案（如果存在的话）。

输入格式

第一行包含一个正整数 $n$ ($1 \le n \le 500\,000$)，表示障碍物的数量。 接下来的 $n$ 行中，第 $i$ 行包含整数 $x_i$ 和 $y_i$ ($0 \le |x_i|, |y_i| \le 10^9$) 以及一个字符 $c_i$ ('/' 或 '\')，描述第 $i$ 个障碍物。没有两个障碍物位于相同的位置。

输出格式

如果没有满足条件的上色方案，仅输出一行 -1。 否则，在唯一的一行中输出一个由空格分隔的 $n$ 个数字（1, 2, 3 或 4）的序列，表示有效的上色方案，即按顺序排列的障碍物颜色。如果存在多个解，输出任意一个即可。

子任务

样例

输入 1

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

输出 1

-1

说明 1

球可能会陷入一个包含 4 次反弹的循环，在给定的 4 个障碍物之间来回反弹。为了使每种颜色出现次数相等，每种颜色应出现一次，但 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

说明 2

球只能陷入一个循环中。下图展示了一种有效的上色方案。从障碍物 1 开始，沿顺时针方向移动，颜色重复为 1 3 1 4 2 3 2 4。

输入 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