To zadanie będzie wykorzystane na obozie Petrozavodsk 2007. Jeśli będziesz na tym obozie, i przypadkiem umiesz po polsku :), to nie czytaj!
Jako, że wiosna już przyszła, ogrodnik Piotr postanowił zasadzić kwiatki w swoim ogrodzie. Ogród Piotra jest nieskończoną płaszczyzną z naniesionym układem współrzędnych. W N (1 ≤ N ≤ 100000) punktach kratowych (tzn. tych o obu współrzędnych całkowitych) Piotr postanowił posadzić po jednym kwiatku - róży lub goździku. Ogrodnik będzie uważał, że jego ogród jest piękny tylko wtedy, gdy na każdej prostej równoległej do którejkolwiek osi układu (tzn. poziomej lub pionowej) liczba róż i goździków będzie się różniła co najwyżej o 1.
Pomóż Piotrowi upiększyć jego ogród!
W pierwszej linii będzie podana liczba N (1 ≤ N ≤ 100000), zaś w N kolejnych liniach po dwie liczby całkowite określające współrzędną x-ową i y-ową kolejnego miejsca, w którym Piotr chce posadzić kwiatka. Wszystkie podane na wejściu punkty będą parami różne, zaś wartości bezwzględne ich współrzędnych nie będą przekraczały 109.
1Jeśli nie ma możliwości posadzenia kwiatków tak, by ogród stał się piękny, wyjście powinno zawierać jedną linię ze słowem IMPOSSIBLE. W przeciwnym razie wyjście powinno się składać z dokładnie N linii. W i-tej linii powinno się znaleźć słowo ROSE, jeśli w i-tym punkcie w kolejności pojawiania się na wejściu powinna być posadzona róża lub CARNATION jeśli goździk. Jeśli jest wiele możliwych wyjść, Twój program powinien wypisać dowolne z nich.
Dla danych wejściowych:
7 2 1 3 1 2 2 1 2 1 3 3 2 2 3
jednym z poprawnych wyników jest:
CARNATION ROSE ROSE CARNATION ROSE CARNATION CARNATION
[Zgłoś rozwiązanie] [Moje zgłoszenia]