Разноцветные точки

Рассмотрим nn точек на плоскости, пронумерованных от 11 до nn, обозначим их как P1,P2,...,PnP_1, P_2, . . . , P_n, координаты ii-й точки (xi,yi)(x_i, y_i).

Рассмотрим следующий процесс. Выберем номер начальной точки ii и номер следующей за ней точки jj (iji \ne j), а также целое число tt. После этого номер прицельной точки kk вычисляется по следующему алгоритму. Рассмотрим вектор PiPj\overrightarrow{P_iP_j} , направленный из точки PiP_i в точку PjP_j . Упорядочим все точки, кроме jj-й, по углу, отсчитывая против часовой стрелки от направления вектора, равного PiPj\overrightarrow{P_iP_j} , отложенного из точки jj. При равенстве угла будем упорядочивать точки по возрастанию расстояния до точки jj. В качестве точки kk выбирается точка, являющаяся tt-й в данном порядке при нумерации с единицы. Далее точка jj становится начальной, а точка kk — следующей за ней, после чего, пользуясь тем же алгоритмом, вычисляется номер прицельной точки. Этот процесс повторяется до бесконечности.

Для лучшего понимания процесса рассмотрим следующий пример. Пусть имеются 66 точек, изображенных на рисунке 11, а t=4t = 4. Пусть номер начальной точки равен 11, а номер следующей за ней точки равен 22. Отложим вектор P1P2\overrightarrow{P_1P_2} от точки P2P_2 и отсортируем все точки, кроме точки P2P_2, по углу, отсчитывая против часовой стрелки от направления данного вектора. На рисунке 2 отложенный вектор обозначен пунктирной линией, а также для удобства проведены векторы из точки P2P_2 во все остальные точки.

Рисунок 1: Пример множества из 6 точек.

Рисунок 2: Вектор P1P2\overrightarrow{P_1P_2}, а также векторы из точки P2P_2 во все остальные точки.

Точки будут упорядочены следующим образом: P3,P5,P1,P6,P4P_3, P_5, P_1, P_6, P_4. Таким образом, номер прицельной точки равен 66. Далее точка 22 становится начальной, а точка 66 — следующей.

На рисунке 3 изображен процесс для начальной точки 22 и следующей точки 66. Точки будут упорядочены следующим образом: P4,P3,P2,P1,P5P_4, P_3, P_2, P_1, P_5. Обратите внимание, что точка P1P_1 в этом списке находится раньше, чем точка P5P_5, так как расстояние от точки P1P_1 до точки P6P_6 меньше, чем расстояние от точки P5P_5 до точки P6P_6. Прицельная точка будет иметь номер 11.

На рисунке 4 изображен процесс для начальной точки 66 и следующей точки 11. Обратите внимание, что в данном случае вектор P6P1\overrightarrow{P_6P_1}, отложенный из точки P1P_1 совпадает с вектором P1P5\overrightarrow{P_1P_5}, отложенным из точки P1P_1. Эти векторы изображены сплошной линией. Точки будут упорядочены следующим образом: P5,P6,P4,P2,P3P_5, P_6, P_4, P_2, P_3. Прицельная точка будет иметь номер 22. Таким образом, далее процесс начнется для начальной точки 11 и следующей точки 22 и зациклится:

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

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

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

Входные данные

Первая строка содержит два целых числа nn и tt (2n10002 \le n \le 1 000, 1tn11 \le t \le n − 1).

Каждая из следующих nn строк содержит два целых числа xix_i и yiy_i (109xi−10^9 \le x_i, yi109y_i \le 10^9).

Гарантируется, что никакие две точки не совпадают.

Выходные данные

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

Подзадачи

баллынеобх. подзадачиограничения
0

0

-

Тесты из условия

1

10

-

n10n \le 10, все точки расположены на одной прямой

2

15

1

Все точки расположены на одной прямой

3

10

-

n10n \le 10, гарантируется, что нет синих точек

4

10

1, 3

n10n \le 10

5

15

3

n100n \le 100, гарантируется, что нет синих точек

6

15

1, 3, 4, 5

n100n \le 100

7

5

-

n>3n > 3, все точки являются вершинами строго выпуклого многоугольника и даны в порядке обхода против часовой стрелки

8

20

1, 2, 3, 4, 5, 6, 7

Нет доп. огранчений

STDINSTDOUT
6 4
-1 -1
1 -2
4 -2
2 -4
2 3
-4 -5
GGBBRG
2 1
1 1
2 2
GG

Примечание

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

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

Для начальной точки 3 и следующей точки 1 точки будут упорядочены следующим образом: P6,P4,P2,P3,P5P_6, P_4, P_2, P_3, P_5. Точка с номером 3 становится прицельной. Далее для начальной точки 1 и следующей точки 3 точки будут упорядочены следующим образом: P5,P1,P2,P6,P4P_5, P_1, P_2, P_6, P_4. Точка с номером 6 становится прицельной. Наконец, для начальной точки 3 и следующей точки 6 точки будут упорядочены следующим образом: P4,P3,P2,P1,P5P_4, P_3, P_2, P_1, P_5. Точка с номером 1 становится прицельной. Далее процесс продолжится с начальной точкой 6 и следующей точкой 1. Из примера, описанного выше в условии задачи, мы знаем, что процесс зациклится, посещая точки с номерами 6, 1 и 2.

Рисунок 5: Процесс для начальной точки 3 и следующей точки 1.

Рисунок 6: Процесс для начальной точки 1 и следующей точки 3.

Рисунок 7: Процесс для начальной точки 3 и следующей точки 6.

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