Mirko and Slavko stumbled upon an old pinball machine. The game consists of a small metal ball that
moves inside the machine, hitting and bouncing off some obstacles.
The game takes place on a board which is represented by a plane and \(n\) obstacles are given in this plane.
An obstacle is represented by a line segment of unit length tilted at a \(45^{◦}\)angle with respect to the
coordinate axes. An obstacle is uniquely described by the position of its midpoint (\(x\)\(i\), y\(i\)) and a character
which is either ’/’ or ’\’ that denotes the orientation of the obstacle. In the plane there is also a ball
which is moving in one of the four directions parallel to the axes at all times. If the ball hits an obstacle,
the direction of its movement changes by \(90^{◦}\)and the ball continues moving. Note that the obstacles are
t\(wo-si\)ded, meaning that the ball is able to bounce off both sides of the obstacle
Mirko and Slavko decided to restore the pinball machine with a new layer of paint. At their disposal are
four buckets of paint containing four different colors. They want to paint each obstacle in one of these
four colors.
Mirko: “You know, I’ve been thinking. There are only two possibilities for the path the ball could take.”
Slavko: “What do you mean?”
Mirko: “Well, either the ball will get stuck in a cycle, periodically repeating the same sequence of bounces,
or at some point it will fly off to infintiy.”
Slavko: “Hm, you’re right. Then maybe we could try to color the obstacles so that for each cycle each
of the colors appears an equal number of times in the cycle and so that this number is even. For example,
if some cycle consists of 24 bounces, we should make it so that there are 6 bounces for each color, and 6 is
an even number.”
Mirko: “And what if there is no such coloring?”
Slavko: “You know the drill, just s\(ay -1\).”
Help Mirko and Slavko determine a coloring of the obstacles which satisfies the required condition, if there
is one.

Subtask 1 (20 points): \(1 \le n \le 40\).

Subtask 2 (20 points): There is at most one cycle in which the ball can get stuck.

Subtask 3 (70 points): No additional constraints.

The first line contains a positive integer \(n\) (\(1 \le n \le 500\,000\)), the number of obstacles.
The \(i-th\) of the next \(n\) lines contains integers \(x@@RISE_MATH_BLOCK_0@@i\) (0 ≤|\(x@@RISE_MATH_BLOCK_1@@i\)| ≤\(10^{9}\)) and a character \(c\)\(i\) (’/’ or
’\’) which describe the \(i-th\) obstacle. No two obstacles have the same position.

If there is no coloring which satisfies the required condition, in the only line pri\(nt -1\).
Otherwise, in the only line print a sequence of \(n\) numbers 1,2,3 or 4 separated by spaces, representing a
valid coloring, the colors of the obstacles in order. If there is more than one solution, print any.

생성자가 기록되지 않았습니다.

출처 COCI 2021/2022 Contest 5