Pinball Machine Coloring

We are given an old pinball machine with (n) bumpers. The game is played on a two-dimensional plane. Each bumper is a plank of unit length oriented at a 45° angle (i.e. its two endpoints make a 45° angle with the coordinate axes). A bumper is described by its center coordinates ((x_i,y_i)) and one of the two characters, '/' or '\', indicating its orientation. When a ball hits a bumper, its direction rotates by 90° – for a bumper marked '/' the ball rotates by +90° (counterclockwise), and for a bumper marked '\' it rotates by -90° (clockwise). (Note that both sides of a bumper cause the deflection.)\n\nIt turns out that when the ball is inside the machine its fate is one of the following two outcomes:

1. It escapes by moving indefinitely in one direction without hitting any further bumpers.
2. It gets caught in a cycle, bouncing among bumpers forever.

During the refurbishment of the machine, four different dyes (colors) are available. The task is to color every bumper with one of these four colors so that in every cycle (if one exists) the number of times each color is encountered is identical and, moreover, this common number is even. (If a bumper is visited more than once in the cycle, it is counted each time according to its color.)\n\nYour task is to either provide a valid coloring, outputting the color assigned to each bumper in the input order, or determine that no such coloring exists and output -1.\n\nNote:\nA bumper that is never part of any cycle may be assigned an arbitrary color since the cycle condition only needs to hold for cycles. All formulas are given in LaTeX format.

inputFormat

The first line contains an integer (n) (the number of bumpers). Each of the next (n) lines contains two integers (x_i) and (y_i) and a character (either '/' or '\') separated by spaces, representing the center of a bumper and its orientation.

outputFormat

If a valid coloring exists, output a single line with (n) space‐separated integers (each from the set ({0, 1, 2, 3})) representing the color assigned to each bumper in the input order. If no valid coloring exists, output a single line containing -1.

sample

1
0 0 /

-1