시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 1024 MB 23 7 6 30.000%

문제

이세계로 떨어져 슬라임 연구를 하던 ntopia를 기억하는가? 그는 슬라임 연구를 성공적으로 끝마치고 지구로 돌아갈 수 있게 되었다. 하지만 ntopia의 직업은 사실 슬라임 연구자가 아니었다. 그는 슬라임을 지구로 몰래 들여가 비싼 값에 팔 속셈으로 슬라임 연구자로 위장하고 이세계에 들어온 슬라임 밀수업자였다!

이세계의 슬라임은 빨간색, 파란색, 노란색의 세 가지 종류가 있다. 이들은 서로 다른 색의 두 슬라임이 합쳐지면 나머지 색의 슬라임 두 마리로 분열하는 성질을 가지고 있다. 예를 들어 빨간색 슬라임과 파란색 슬라임이 합쳐지면 노란색 슬라임 두 마리가 된다. 그러나 같은 색의 슬라임은 서로 합쳐질 수 없다.

귀여운 슬라임

ntopia는 격자 모양으로 칸이 나뉘어진 상자에 한 칸에 한 마리씩 슬라임을 잡아넣었다. ntopia의 의도를 눈치챈 슬라임들은 가치를 떨어뜨리기 위해 서로 합체와 분열을 반복해서 모두 같은 색이 되려고 한다. 그러나 슬라임들은 먼 거리를 점프할 수 없기 때문에 상하좌우로 인접한 칸에 있는 슬라임과만 합쳐질 수 있으며, 분열된 두 슬라임은 다시 원래 각자의 위치로 떨어진다. 게다가 ntopia는 곧 상자를 들고 지구로 출발할 예정이기 때문에 슬라임들에게는 최대 100만 번의 합체를 할 시간밖에 남아 있지 않다.

슬라임들의 배치가 주어질 때 슬라임들이 목표를 달성할 수 있을지 확인해 보자.

입력

첫 줄에 상자의 세로 방향의 칸의 개수와 가로 방향의 칸의 개수를 의미하는 정수 NM(1 ≤ N, M ≤ 200)이 주어진다.

다음 N개의 줄에 걸쳐 각 줄에 슬라임들의 배치를 의미하는 M글자의 문자열이 하나씩 주어진다. 문자열은 문자 R, B, Y로만 이루어져 있으며, 각각 빨간색, 파란색, 노란색 슬라임을 의미한다.

출력

슬라임들이 목표를 달성할 수 있다면 첫 줄에 필요한 합체 횟수를 의미하는 정수 K(0 ≤ K ≤ 1,000,000)를 출력한다.

다음 K줄에 걸쳐 각 줄에 합쳐지는 두 슬라임의 위치를 나타내는 네 개의 정수 x1, y1, x2, y2(1 ≤ x1, x2N, 1 ≤ y1, y2M)를 공백으로 구분하여 출력한다. 이는 x1y1열에 있는 슬라임과 x2y2열에 있는 슬라임이 합쳐짐을 의미한다.

슬라임들이 목표를 달성할 수 없다면 첫 줄에 -1를 출력한다.

예제 입력 1

2 2
RB
BY

예제 출력 1

4
1 1 1 2
1 1 2 1
1 1 1 2
2 1 2 2

예제 입력 2

1 3
RRB

예제 출력 2

-1