Petya drew n circles on paper and connected some pairs of circles with lines. After that, he colored each circle in one of the three colors – red, blue or green.
Now Petya wants to change their coloring. Namely – he wants to recolor each circle with some other color so that no two circles of the same color are connected by a line. At the same time, he wants to necessarily recolor each circle, and repainting the circle in the same color as it was originally painted is not allowed.
Help Petya decide what colors the mugs should be repainted in order to fulfill the specified condition.
Input
The first line contains two integers n and m – the number of circles and the number of lines drawn by Petya, respectively (1 ≤ n ≤ 1000, 0 ≤ m ≤ 20000).
The next line contains n characters from the set {'R', 'G', 'B'} – The i-th of these symbols means the color of the i-th circle ('R' – red, 'G' – green, 'B' &ndash ; blue).
Then m lines contain two integers – pairs of circles connected by segments.
Imprint
Print one line consisting of n characters from the set {'R', 'G', 'B'} – the colors of the circles after repainting. If there are several solutions, print any one.
If there is no solution, print the word "Impossible''.
Examples
| # |
Input |
Output |
| 1 |
4 5
RRRG
1 3
14
34
24
2 3
| BBGR |
| 2 |
4 5
RGRR
1 3
14
34
24
2 3
| Impossible |