Задача A. Взлом шифра ≡

Условие

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

Замок представляет собой n кнопок, пронумерованных целыми числами от 1 до n. Замок открывается только тогда, когда какие-то последовательные n нажатий на кнопки образуют некоторую секретную перестановку. Кнопки замка следует нажимать по очереди, нажать одновременно две или более кнопки нельзя.

Более формально: предположим, что Алан нажал на кнопки k раз. Пусть a_i (1 ≤ i ≤ k) — номер кнопки, которую Алан нажал i по счету, а b₁, b₂, …, b_n — секретная перестановка. Тогда замок открывается, если существует такое число x (1 ≤ x ≤ k − n + 1), что b₁ = a_x, b₂ = a_x+1, …, b_n = a_x+n−1.

Алан хочет придумать такую универсальную последовательность нажатий, что при нажатии кнопок в такой последовательности замок откроется для любой секретной перестановки. Также Алан хочет, чтобы эта последовательность не была слишком длинной, а именно, ее длина не превышала 2 n!, где n! = 1 ⋅ 2 ⋅ … ⋅ n. Например, для n = 3 длина последовательности не должна превышать 12.

Помогите Алану найти такую последовательность.

Формат входного файла

В единственной строке входного файла находится целое число n (1 ≤ n ≤ 9) — количество кнопок на кодовом замке.

Формат выходного файла

В первой строке выходного файла выведите число k (0 ≤ k ≤ 2 n!) — длину универсальной последовательности. Во второй строке выведите k целых чисел a_i, разделенных пробелами (1 ≤ a_i ≤ n) — порядок, в котором следует нажимать кнопки. Обратите внимание, что достаточно вывести любую последовательность длины не более 2 n!, минимизировать длину не нужно. Гарантируется, что такая последовательность существует для любого n.

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

2

3
1 2 1

3

10
1 2 3 1 3 2 1 3 1 2

Задача B. Разделение королевства ≡

Условие

Королевство Флатландия имеет вид бесконечной двумерной плоскости. В королевстве находится n замков. Для более удобного составления карт в Флатландии была введена Декартова система координат. Известно, что i-й замок находится в точке с координатами (x_i+0.5, y_i+0.5), где x_i, y_i — целые числа. Местоположения всех замков попарно различны.

На старости лет король решил разделить на карте королевство между своими сыновьями прямыми, параллельными осям координат. Если прямая параллельна оси Ox, то y координата у всех точек на прямой должна быть целым числом, иначе x координата у всех точек должна быть целым числом. В обоих случаях соответствующие целые координаты по модулю не должны превышать 2 ⋅ 10⁹. При этом Его величество хочет, что бы после разделения королевства любые два замка оказались бы в различных частях.

Помогите королю разделить королевство, используя не более чем n−1 прямую. У любой пары прямых должно быть не более одной общей точки.

Формат входного файла

В первой строке задано целое число n (1 ≤ n ≤ 100 000) — количество замков в королевстве. В следующих n строках записано по два числа x_i и y_i (−10⁹ ≤ x_i ≤ 10⁹, −10⁹ ≤ y_i ≤ 10⁹) — целые части координат замков.

Формат выходного файла

В первой строке выходного файла выведите количество используемых прямых. В следующих строчках выведите сами прямые, по одной в каждой строке. Если прямая параллельна оси Ox, то выведите символ y, а затем через пробел y координату всех точек на этой прямой, иначе выведите символ x, а затем через пробел x координату всех точек на этой прямой.

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

4
0 2
0 3
1 2
1 3

2
x 1
y 3

Задача C. Ставка ≡

Условие

Андрей очень любит играть в Космический покер.

В космическом покере вместо карт используются фишки трех цветов. Казино определяет два числа A и C — коэффициенты для вычисления ставок. Затем игрок по определенным правилам ставит фишки трех цветов: красного, зеленого и синего. Выигрыш игрока вычисляется по формуле: A⋅ (r² + g² + b²) + C ⋅ min { r, g, b}, где r, g, b — количество фишек красного, зеленого и синего соответственно.

Правила, по которым делаются ставки, очень сложны, но сейчас перед Андреем стоит следующая задача. На поле уже есть r красных, g зеленых и b синих фишек. Прежде чем будет определен его выигрыш, он может добавить на поле ровно одну фишку любого цвета. Помогите ему выбрать цвет фишки, которую следует добавить на поле, чтобы максимизировать выигрыш.

Формат входного файла

Во входном файле содержится несколько игровых ситуаций, которые требуется проанализировать.

В первой строке задано одно целое число t (1 ≤ t ≤ 10 000) — количество игровых ситуаций.

Каждая игровая ситуация описывается двумя строками. В первой строке задано два целых числа A и C (1 ≤ A, C ≤ 10) — коэффициенты для вычисления выигрыша. Во второй строке задано три целых числа r, g и b (0 ≤ r, g, b ≤ 15) — количество фишек красного, зеленого и синего цвета, соответственно.

Формат выходного файла

Выведите t строк. В k-ой строке выведите RED, если оптимально добавить красную фишку, GREEN, если оптимально добавить зеленую фишку или BLUE, если оптимально добавить синюю фишку. Если есть несколько оптимальных вариантов, можно вывести любой из них

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

3
2 10
2 4 4
1 2
3 4 5
4 2
7 7 7

RED
BLUE
GREEN