Problem Description

There is an old pinball machine containing $n$ flippers.

The game takes place in a two-dimensional plane, where each flipper forms a $45^\circ$ acute angle with the coordinate axes and has a length of 1 unit. Each flipper is represented by its center coordinates $(x_i, y_i)$ and a character '/' or '\'. When a ball hits a flipper, its direction of motion will rotate by $90^\circ$. Note that both sides of the flipper can deflect the ball's direction.

It is easy to see that when a ball is in the pinball machine, it has only two possible outcomes:

• It continues to move in a certain direction without hitting any flippers.
• It gets trapped in a cycle of flippers.

During the renovation of the pinball machine, four colors of dye are available. The goal is to color each flipper in such a way that every cycle passes through each color an equal and even number of times.

Provide a coloring method that meets the criteria, or prove that such a method does not exist. If it does not exist, output -1.

Input Format

The first line contains a positive integer $n$, representing the number of flippers.

The next $n$ lines each contain two positive integers $x_i, y_i$ and a character $c_i$ ('/' or '\'), representing a flipper. It is guaranteed that the positions of the flippers do not overlap.

Output Format

If there is no valid coloring method, output -1.

Otherwise, output $n$ integers from 1 to 4, representing the colors chosen for the $n$ flippers. If there are multiple valid solutions, output any one of them.

Sample Input and Output

Sample Input #1

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

Sample Output #1

-1

Sample Input #2

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

Sample Output #2

1 3 2 4 1 3 2 4 1

Sample Input #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 \

Sample Output #3

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

Notes

[Sample 2 Diagram]

[Data Range and Constraints]

This problem is bundled with subtasks.

• Subtask 1 (20 pts): $1 \le n \le 40$.
• Subtask 2 (20 pts): There is at most one cycle.
• Subtask 3 (70 pts): No additional constraints.

For $100\%$ of the data, $1 \le n \le 5 \times 10^5$, $0 \le |x_i|, |y_i| \le 10^9$.

[Source] COCI 2021-2022#5 Task 3 Fliper.

见题面 Input 部分

见题面 Output 部分