Problem Description

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

The game takes place on a 2D plane. Each flipper always forms an acute angle of $45^\circ$ with the coordinate axes and has length $1$ unit. A flipper is described by its center coordinates $(x_i,y_i)$ and a character / or . After the ball hits a flipper, its moving direction rotates by $90^\circ$. Note that both sides of a flipper can deflect the ball’s direction.

It is not hard to see that when the ball is inside the pinball machine, it has only two possible outcomes:

• It keeps moving forever in some direction without hitting any flipper.
• It gets trapped in a cycle among several flippers.

During the refurbishment of the pinball machine, there are four colors of dye available. Now we want to color every flipper in the pinball machine so that, in every cycle, the number of times each color is passed through is the same and is even.

Please output a coloring that satisfies the requirement, or prove that such a coloring does not exist. If it does not exist, output -1.

Input Format

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

Each of the next $n$ lines contains two positive integers $x_i,y_i$ and a character $c_i$ (/ or ), describing a flipper. The input guarantees that flipper positions do not coincide.

Output Format

If no coloring satisfies the requirement, output -1.

Otherwise output $n$ integers in $1 \sim 4$, representing the dye color chosen for each of the $n$ flippers. If there are multiple valid colorings, output any one of them.

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

Hint

[Diagram for Sample 2]

[Constraints]

This problem uses bundled testdata.

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

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

[Notes]

This problem uses a self-written Special Judge. If you have any questions about this or want to hack, please private message the author or make a post.

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

Translated by ChatGPT 5