32113번 - 배고픈 무토를 위한 피자 만들기 스페셜 저지

문제

키네시스는 검은 마법사를 토벌하기 위해 츄츄 아일랜드를 탐험하던 중 배고픈 무토를 마주쳤다. 무토를 위해 매일 밥을 주고 있던 시미아는 밥투정하고 있는 무토를 위한 대형 피자를 만들기 위해 키네시스에게 도움을 요청했다. 큰 덩치를 가진 무토는 검은 마법사한테 가는 길을 막고 있기 때문에 키네시스는 어쩔 수 없이 시미아의 부탁을 들어주기로 했다.

무토가 원하는 커다란 피자는 $N\times N$ 크기의 격자 모양이며, 피자의 가장 왼쪽 위 칸은 1ドル$행 1ドル$열이고, 가장 오른쪽 아래 칸은 $N$행 $N$열이다. 시미아가 준 레시피에는 피자에 올려야 하는 미트볼의 배치가 그려져 있으며, 키네시스는 레시피에 그려진 대로 미트볼을 토핑해야 한다. 처음에는 피자의 $R$행 $C$열에 시미아가 먼저 토핑한 미트볼이 하나 놓여 있다. 미트볼의 모양은 격자의 칸과 정확히 일치하며 격자 한 칸에 두 개 이상의 미트볼이 들어갈 수 없다.

N = 5, R = 3, C = 2일 때 피자의 상태와 피자 밖에서 염동력을 사용할 수 있는 위치

$N = 5,ドル $R = 3,ドル $C = 2$일 때 피자의 상태와 피자 밖에서 염동력을 사용할 수 있는 위치

피자를 밟으면 먹을 수 없게 되어 버리기 때문에 키네시스는 피자 밖에서 염동력을 사용하여 피자를 완성해야 한다. 염동력을 1ドル$회 사용하는 과정은 아래와 같다.

1. 염동력을 사용할 위치를 정한다. 가능한 위치는 피자의 위쪽, 아래쪽, 왼쪽, 오른쪽 중 하나이다. 염동력은 키네시스가 위치한 곳에서 시작하여 위쪽이면 행이 증가하는 방향으로, 아래쪽이면 행이 감소하는 방향으로, 왼쪽이면 열이 증가하는 방향으로, 오른쪽이면 열이 감소하는 방향으로 사용한다.
2. 염동력을 사용할 행 또는 열의 번호를 정한다. 염동력은 행 또는 열과 평행하도록 사용해야 하며, 두 개 이상의 행 또는 열에 걸쳐서 사용할 수 없다.
3. 염동력을 사용한다. 사용할 수 있는 염동력은 두 종류이다.
   • 밀어넣기(push): 미트볼을 밀어 넣어서 처음 부딪힌 미트볼의 바로 앞 칸에 놓는다. 만약 밀어 넣기 전 염동력을 사용한 방향의 첫 번째 칸에 미트볼이 있거나, 그 방향에 미트볼이 없어서 밀어 넣은 미트볼이 피자 안에 위치할 수 없다면 밀어 넣은 미트볼은 사라진다.
   • 당기기(pull): 염동력에 처음 맞은 미트볼을 피자 밖으로 꺼낸다. 염동력을 사용한 방향에 미트볼이 없다면 아무 일도 일어나지 않는다.

밀어넣기(push), 당기기(pull) 염동력을 사용하는 모습

밀어넣기(push), 당기기(pull) 염동력을 사용하는 모습

시미아의 레시피대로 피자를 토핑했다면 무토가 피자를 맛있게 먹고 다음 지역으로 갈 수 있는 길을 열어줄 것이다. 하지만 검은 마법사가 언제 세상을 파멸시킬지 모르기 때문에 키네시스는 피자를 만드는 데에 시간을 지체할 수 없다.

염동력을 2ドルN^2$번 이하로 사용하여 피자를 완성하는 방법 중 하나를 출력해 보자.

입력

첫 줄에 피자의 크기 $N$이 주어진다. (3ドル\leq N\leq 50$)

둘째 줄에 시미아가 처음에 토핑한 미트볼의 행과 열을 의미하는 정수 $R,ドル $C$가 공백을 사이에 두고 주어진다. (1ドル\leq R,C\leq N$)

이후 $N$개의 줄에 걸쳐 시미아의 레시피대로 그려진 미트볼 배치가 주어진다. 각 줄에는 길이가 $N$인 문자열이 주어진다. 레시피의 $i$번째 줄의 $j$번째 문자는 $i$행 $j$열의 미트볼 여부를 의미하며 .는 빈 칸, #는 미트볼이 놓인 칸을 의미한다.

출력

만약 염동력을 2ドルN^2$번 이하로 사용하여 피자를 완성할 수 있다면 첫 줄에 키네시스가 사용한 염동력의 횟수 $M$을 출력한다. 단, $M$이 최소일 필요는 없다. (0ドル\leq M\leq 2N^2$)

$M$이 1ドル$ 이상이라면 둘째 줄부터 $M$개의 줄에 걸쳐 키네시스가 수행한 행동을 한 줄에 하나씩 출력한다. 각 줄에는 염동력을 사용한 위치 (위쪽: U, 아래쪽: D, 왼쪽: L, 오른쪽: R), 행 또는 열의 번호 $X$ (1ドル\leq X\leq N$), 염동력의 종류(밀어넣기는 push, 당기기는 pull)을 공백으로 구분하여 출력한다.

만약 염동력을 2ドルN^2$번 이하로 사용하여 피자를 완성할 수 없다면 첫 줄에 -1만을 출력한다.

제한

힌트