C. Бомбы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Вас есть робот, задачей которого является уничтожение бомб, расположенных на координатной плоскости. А именно, на координатной плоскости расположены n бомб, причем i-ая бомба расположена в точке с координатами (xi, yi). Известно, что никакие две бомбы не расположены в одной точке и что никакая бомба не расположена в точке с координатами (0, 0).

Изначально робот расположен в точке с координатами (0, 0). Для удобства будем обозначать парой (x, y) — текущее положение робота. Для того, чтобы уничтожить все бомбы, робот должен выполнить несколько операций, каждая операция одного из следующих трех типов:

  1. Формат операции — «1 k dir». Во время выполнения операции робот k (k ≥ 1) раз перемещается в направлении dir. Всего робот может двигаться только в 4 направления: «R», «L», «U», «D». За одно перемещение в зависимости от направления dir робот переходит в одну из следующих точек: (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1) (точки заданы соответственно направлениям). Запрещено выполнять перемещение из точки (x, y), если хотя бы одна из точек пути (кроме точки, в которую мы в конечном итоге придем k-ым перемещением) содержит бомбу.
  2. Формат операции — «2». Во время выполнения операции робот поднимает бомбу в точке (x, y) и кладет ее в специальный контейнер, расположенный в роботе. Таким образом робот может переносить бомбу из любой точки в любую другую точку. Операцию запрещено выполнять, если в точке (x, y) нет бомбы. Запрещено поднимать бомбу, если в контейнере у робота уже есть бомба.
  3. Формат операции — «3». Во время выполнения операции робот достает бомбу из контейнера и уничтожает ее. Разрешается выполнять эту операцию, только если робот находится в точке (0, 0). Запрещено выполнять операцию, если в контейнере нет бомбы.

Помогите роботу, найдите последовательность операций минимальной длины, с помощью которой робот уничтожит все бомбы на координатной плоскости.

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

В первой строке записано единственное целое число n (1 ≤ n ≤ 105) — количество бомб на координатной плоскости. В следующих n строках содержится по два целых числа. В i-ой строке содержатся числа xi, yi ( - 109 ≤ xi, yi ≤ 109) — координаты i-ой бомбы. Гарантируется, что никакие две бомбы не содержатся в одной точке и что никакая бомба не расположена в точке (0, 0).

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

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

Примеры
Входные данные
2
1 1
-1 -1
Выходные данные
12
1 1 R
1 1 U
2
1 1 L
1 1 D
3
1 1 L
1 1 D
2
1 1 R
1 1 U
3
Входные данные
3
5 0
0 5
1 0
Выходные данные
12
1 1 R
2
1 1 L
3
1 5 R
2
1 5 L
3
1 5 U
2
1 5 D
3