Three planets $$$X$$$, $$$Y$$$ and $$$Z$$$ within the Alpha planetary system are inhabited with an advanced civilization. The spaceports of these planets are connected by interplanetary space shuttles. The flight scheduler should decide between $$$1$$$, $$$2$$$ and $$$3$$$ return flights for every existing space shuttle connection. Since the residents of Alpha are strong opponents of the symmetry, there is a strict rule that any two of the spaceports connected by a shuttle must have a different number of flights.

For every pair of connected spaceports, your goal is to propose a number $$$1$$$, $$$2$$$ or $$$3$$$ for each shuttle flight, so that for every two connected spaceports the overall number of flights differs.

You may assume that:

1) Every planet has at least one spaceport

2) There exist only shuttle flights between spaceports of different planets

3) For every two spaceports there is a series of shuttle flights enabling traveling between them

4) Spaceports are not connected by more than one shuttle

Input

The first row of the input is the integer number $$$N$$$ $$$(3 \leq N \leq 100 000)$$$, representing overall number of spaceports. The second row is the integer number $$$M$$$ $$$(2 \leq M \leq 100 000)$$$ representing number of shuttle flight connections.

Third row contains $$$N$$$ characters from the set $$$\{X, Y, Z\}$$$. Letter on $$$I^{th}$$$ position indicates on which planet is situated spaceport $$$I$$$. For example, "XYYXZZ" indicates that the spaceports $$$0$$$ and $$$3$$$ are located at planet $$$X$$$, spaceports $$$1$$$ and $$$2$$$ are located at $$$Y$$$, and spaceports $$$4$$$ and $$$5$$$ are at $$$Z$$$.

Starting from the fourth row, every row contains two integer numbers separated by a whitespace. These numbers are natural numbers smaller than $$$N$$$ and indicate the numbers of the spaceports that are connected. For example, "$$$12\ 15$$$" indicates that there is a shuttle flight between spaceports $$$12$$$ and $$$15$$$.

Output

The same representation of shuttle flights in separate rows as in the input, but also containing a third number from the set $$$\{1, 2, 3\}$$$ standing for the number of shuttle flights between these spaceports.

Alpha planetary system

Examples