Задача 4. Разноцветные точки ≡

Условие

Рассмотрим n точек на плоскости, пронумерованных от 1 до n, обозначим их как P₁, P₂, …, P_n, координаты i-й точки (x_i, y_i).

Рассмотрим следующий процесс. Выберем номер начальной точки i и номер следующей за ней точки j (i ≠ j), а также целое число t. После этого номер прицельной точки k вычисляется по следующему алгоритму. Рассмотрим вектор overrightarrowP_i P_j, направленный из точки P_i в точку P_j. Упорядочим все точки, кроме j-й, по углу, отсчитывая против часовой стрелки от направления вектора, равного overrightarrowP_i P_j, отложенного из точки j. При равенстве угла будем упорядочивать точки по возрастанию расстояния до точки j. В качестве точки k выбирается точка, являющаяся t-й в данном порядке при нумерации с единицы. Далее точка j становится начальной, а точка k — следующей за ней, после чего, пользуясь тем же алгоритмом, вычисляется номер прицельной точки. Этот процесс повторяется до бесконечности.

Для лучшего понимания процесса рассмотрим следующий пример. Пусть имеются 6 точек, изображенных на рисунке 1, а t = 4. Пусть номер начальной точки равен 1, а номер следующей за ней точки равен 2. Отложим вектор overrightarrowP₁ P₂ от точки P₂ и отсортируем все точки, кроме точки P₂, по углу, отсчитывая против часовой стрелки от направления данного вектора. На рисунке 2 отложенный вектор обозначен пунктирной линией, а также для удобства проведены векторы из точки P₂ во все остальные точки.

Точки будут упорядочены следующим образом: P₃, P₅, P₁, P₆, P₄. Таким образом, номер прицельной точки равен 6. Далее точка 2 становится начальной, а точка 6 — следующей.

На рисунке 3 изображен процесс для начальной точки 2 и следующей точки 6. Точки будут упорядочены следующим образом: P₄, P₃, P₂, P₁, P₅. Обратите внимание, что точка P₁ в этом списке находится раньше, чем точка P₅, так как расстояние от точки P₁ до точки P₆ меньше, чем расстояние от точки P₅ до точки P₆. Прицельная точка будет иметь номер 1.

На рисунке 4 изображен процесс для начальной точки 6 и следующей точки 1. Обратите внимание, что в данном случае вектор overrightarrowP₆ P₁, отложенный из точки P₁ совпадает с вектором overrightarrowP₁ P₅, отложенным из точки P₁. Эти векторы изображены сплошной линией. Точки будут упорядочены следующим образом: P₅, P₆, P₄, P₂, P₃. Прицельная точка будет иметь номер 2. Таким образом, далее процесс начнется для начальной точки 1 и следующей точки 2 и зациклится.

Покрасим каждую из n точек в один из трех цветов. Цвет i-й точки определяется следующим образом:

• Пусть существует такая точка j, что, выбрав точку i в качестве начальной, а точку j в качестве следующей, в результате описанного процесса точка i побывает начальной бесконечное количество раз. В этом случае точка i будет покрашена в зеленый цвет.
• Пусть точка i не была покрашена в зеленый цвет и существует такая точка j, что, выбрав точку i в качестве начальной, а точку j в качестве следующей, в результате описанного процесса точка i побывает начальной еще хотя бы один раз. В этом случае точка i будет покрашена в синий цвет.
• Пусть точка i не была покрашена ни в зеленый, ни в синий цвет. В этом случае точка i будет покрашена в красный цвет.

Для каждой точки определите, в какой цвет ее нужно покрасить.

Формат входных данных

Первая строка содержит два целых числа n и t.

Каждая из следующих n строк содержит два целых числа x_i и y_i. Гарантируется, что никакие две точки не совпадают.

Формат выходных данных

Выведите строку, состоящую из n символов: i-й символ строки должен обозначать цвет i-й точки. Для зеленой точки выведите букву~«G», для синей точки — букву~«B», а для красной точки — букву~«R».

Ограничения

2 ≤ n ≤ 1 000, 1 ≤ t ≤ n − 1

 − 10⁹ ≤ x_i, y_i ≤ 10⁹

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснение к примеру

Рассмотрим некоторые точки из первого примера.

Точка P₁ окрашены в зеленый цвет, потому что можно выбрать точку P₂ в качестве следующей, и процесс посетит точку P₁ бесконечное количество раз. Данный пример был рассмотрен выше в условии задачи.

Можно показать, что точка P₃ не является зеленой, однако она является синей, так как можно выбрать точку 1 в качестве следующей, точка 3 окажется начальной еще хотя бы один раз. Процесс для начальной точки 1 и следующей точки 3 проиллюстрирован на рисунках 5, 6 и 7 ниже.

Для начальной точки 3 и следующей точки 1 точки будут упорядочены следующим образом: P₆, P₄, P₂, P₃, P₅. Точка с номером 3 становится прицельной. Далее для начальной точки 1 и следующей точки 3 точки будут упорядочены следующим образом: P₅, P₁, P₂, P₆, P₄. Точка с номером 6 становится прицельной. Наконец, для начальной точки 3 и следующей точки 6 точки будут упорядочены следующим образом: P₄, P₃, P₂, P₁, P₅. Точка с номером 1 становится прицельной. Далее процесс продолжится с начальной точкой 6 и следующей точкой 1. Из примера, описанного выше в условии задачи, мы знаем, что процесс зациклится, посещая точки с номерами 6, 1 и 2.

Во втором примере из условия легко показать, что если одна из точек является начальной, а другая — следующей, то прицельной станет точка, которая являлась начальной. Поэтому обе точки будут окрашены в зеленый цвет.

Примеры тестов

6 4
-1 -1
1 -2
4 -2
2 -4
2 3
-4 -5

GGBBRG

2 1
1 1
2 2

GG