도형 접기

Petya는 수학 시간이 지루해져서 모눈종이에 정사각형을 칠하기 시작했다. 그것도 지루해졌을 때, 그는 자신이 칠한 칸 k개가 연결된 집합을 이루고 있다는 것을 발견했다. 즉, 어떤 칠한 칸에서든 변을 공유하는 다른 칠한 칸으로 이동해 다른 모든 칠한 칸에 도달할 수 있다.

그는 종이에서 도형을 잘라내고 어떤 모눈선(가로 또는 세로, 어느 쪽이었는지는 기억하지 못한다)을 따라 접었다. 그런 다음 다른 모눈종이의 칸을 칠해 접힌 도형의 복사본을 만들었다. 이제 Petya는 원래 도형을 잃어버렸고, 그에게 남은 것은 접힌 뒤의 복사본뿐이다. 이제 Petya는 원래 도형을 복원하려고 한다.

도형을 정확히 복원하기는 어렵지만, Petya는 접어서 같은 접힌 그림을 얻을 수 있는 k칸짜리 도형이라도 좋다고 결정했다. 그를 도와, 주어진 방식으로 접을 수 있는 연결된 k칸짜리 도형을 하나 찾아라.

예를 들어 두 번째 예제를 보자. 거기에는 뒤집힌 'U' 자와 비슷한 접힌 도형이 있고, 원래 도형은 12칸을 포함한다. 원래 도형이 어떻게 생겼을 수 있는지 한 가지 예가 그림에 나와 있으며, 이는 y = 3인 직선을 따라 접힌 것이다:

입력 데이터는 여러 테스트 케이스를 포함한다. 첫 줄에는 테스트 케이스의 수 t (1 ≤ t ≤ 200)가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다. 설명의 첫 줄에는 두 정수 n, k가 주어진다. n은 접힌 도형에서 칠한 칸의 수이고, k는 원래 도형에서 칠한 칸의 수이다 (1 ≤ n < k ≤ 10^5).

이어지는 n개 줄 각각에는 두 정수 x_i, y_i가 주어진다. 이는 i번째 칠한 칸의 왼쪽 아래 모서리의 좌표이다 (-10^8 ≤ x_i, y_i ≤ 10^8). 모든 칠한 칸은 서로 다르며 연결된 도형을 이룬다는 것이 보장된다.

한 입력 데이터의 모든 테스트 케이스에서 k 값의 합은 10^5을 넘지 않는다.

각 테스트 케이스마다 이 테스트의 답을 출력한다. 도형의 설명과 주어진 도형을 얻기 위해 접는 방법을 출력한다.

첫 줄에는 접는 선의 설명이 들어가야 한다. 이어지는 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와 접는 선의 좌표의 절댓값은 10^9을 넘지 않아야 한다. 요구되는 도형이 존재한다는 것이 보장된다. 가능한 답이 여러 개라면 아무거나 출력한다.