你有一个机器人,它的任务是摧毁方形平面上的炸弹。具体来说,正方形平面包含n个炸弹,第i个炸弹位于坐标为(xi,yi)的点。我们知道没有两颗炸弹位于同一点,也没有炸弹位于坐标为 (0, 0) 的点。最初,机器人位于坐标 (0, 0) 的点。另外,我们将机器人的当前位置标记为 (x, y)。为了销毁所有炸弹,机器人可以执行三种类型的操作:
1. 操作的格式为“1 k dir”。为了执行该操作,机器人必须沿方向 dir k (k ≥ 1) 次移动。机器人只能移动 4 个方向:“R”、“L”、“U”、“D”。在一次移动过程中,机器人可以从当前点移动到以下点之一:(x + 1, y)、(x - 1, y)、(x, y + 1)、(x, y - 1)(对应方向)。如果路径上至少有一个点(除了目的地点)包含炸弹,则禁止从点 (x, y) 移动。
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 的解。
示例
输入 #1
2 1 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
输入 #2
3 5 0 0 5 1 0
输出 #2
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