Отборочный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"C" Складывание фигуры
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

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

Аккуратно вырезав ее из тетради, он сложил ее пополам вдоль линии клетчатой сетки (по горизонтали или по вертикали — он точно не запомнил), а также нарисовал копию сложенной фигуры в тетради. И не зря! Петя потерял фигуру, и все что у него осталось — копия сложенной фигуры, нарисованная в тетради. Теперь он хочет восстановить исходную фигуру.

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

Рассмотрим второй пример теста из условия. В нем сложенная фигура предславляет собой букву «П», а исходная фигура состоит из 12 клеток. Один из возможных вариантов исходной фигуры представлен на рисунке (сгиб происходит по прямой y = 3):

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

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 200).

Каждый из следующих t тестов описывается следующим образом: в первой строке описания теста содержится два целых числа n, k — количество закрашенных клеток, из которых состоит сложенная фигура Васи и количество клеток в исходной фигуре (1 ≤ n < k ≤ 105).

В каждой из следующих n строк содержатся два числа xi, yi — координатылевого нижнего угла i-й закрашенной клетки ( - 108 ≤ xi, yi ≤ 108). Гарантируется, что все закрашенные клетки различны и образуют связную фигуру.

Гарантируется, что сумма k во всех тестах одних входных данных не превосходит 105.

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

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

В первой строке выведите линию сгиба, а в k следующих строках по два целых числа (x'i, y'i) — координаты клеток связной фигуры, которую можно сложить пополам по выведенной линии сгиба, чтобы получить фигуру во входных данных.

Линия сгиба должна быть выведена одним из 4 способов:

  • L num — сгиб производится по прямой x = num, левая часть накладывается поверх правой;
  • R num — сгиб производится по прямой x = num, правая часть накладывается поверх левой;
  • U num — сгиб производится по прямой y = num, верхняя часть накладывается поверх нижней;
  • D num — сгиб производится по прямой y = num, нижняя часть накладывается поверх верхней.

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

Примеры
Входные данные
2
7 14
0 0
0 1
0 2
1 2
2 2
2 1
2 0
7 12
0 0
0 1
0 2
1 2
2 2
2 1
2 0
Выходные данные
L 0
0 0
0 1
0 2
1 2
2 0
2 1
2 2
-1 0
-1 1
-1 2
-2 2
-3 2
-3 1
-3 0
U 3
0 0
0 1
0 2
1 2
2 2
2 1
2 0
0 3
1 3
2 3
0 4
2 4
 

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.