루미너스와 모험 중 마주친 퍼즐게임

빛과 어둠의 마법사 루미너스는 모험을 떠나고 있다. 하지만, 지금 그는 함정이 가득한 미궁 속에 갇힌 상태이다. 루미너스는 빠르게 탈출하기 위해 지름길에 들어섰고, 그 순간 퍼즐게임이라는 이름의 함정 밭과 마주치게 되었다.

그는 빠르게 탈출해야만 하는 이유가 존재했고, 퍼즐게임을 풀기 위해 함정 밭 앞으로 갔다. 그때였다. 갑자기 큰소리와 함께 홀로그램이 생겨났고, 홀로그램 속에는 줄어들고 있는 타이머와 함께 ‘너의 스킬은 한 가지를 제외하고 모두 봉인되었다’라는 메시지가 쓰여있었다. 루미너스는 급하게 “안티 매직쉘!” 이라고 큰 소리로 외쳐보았지만, 그저 공허한 외침이 될 뿐이었다. 결국 그는 퍼즐을 풀지 아니면 지름길을 포기할지 선택해야 했다.

퍼즐게임은 N × M 격자판에서 진행된다. 각 칸에는 빛의 함정 또는 어둠의 함정이 존재한다. 안전하게 지나가기 위해서는 스킬을 사용해 격자판속의 모든 함정을 제거해야 한다.

루미너스가 봉인되지 않은 유일한 스킬은 빛의 퍼니싱 리소네이터이다. 이 스킬은 어둠의 함정에만 사용할 수 있으며, 스킬을 사용하면 대상이 된 어둠의 함정은 제거되고 그 칸에 상하좌우로 인접해 있는 칸의 함정들은 영향을 받아 속성이 뒤집히게 된다.

미궁속에는 함정이 끝도 없이 있기 때문에 이러한 퍼즐을 총 K개나 풀어야 한다. 

각 퍼즐의 상태가 주어졌을 때, 루미너스를 도와 각각의 퍼즐을 해결할 수 있는지 없는지, 있다면 퍼즐을 해결할 방법을 알려주자!

입력은 여러 개의 퍼즐로 이루어진다. 입력의 첫째 줄에는 풀어야 할 퍼즐의 개수 K가 주어지며 그 후 각 퍼즐의 상태에 대한 정보가 차례대로 주어진다.

각 퍼즐의 첫째 줄에는 격자판의 세로 길이 N과 가로 길이 M이 공백을 구분으로 주어진다. 

그 후 N개의 줄에는 퍼즐의 상태를 알려주는 길이 M의 L과 D로 이루어진 문자열이 주어진다. i+1 번째 줄의 j번째 글자가 L이면 격자판상의 i행 j열에 빛의 함정이 있다는 것이고, D면 어둠의 함정이 있다는 것이다.

퍼즐을 풀 수 있는지 여부와 풀 수 있다면 퍼즐을 푸는 방법을 각 퍼즐에 대해 차례대로 출력한다.

루미너스가 퍼즐을 해결할 수 있으면 Solve를 출력하고, 다음 줄부터 NM 개의 줄에 걸쳐서 루미너스가 빛의 퍼니싱 리소네이터를 사용해야 하는 위치를 차례대로 출력한다. 구체적으로 i행 j열의 함정에 k번째로 빛의 퍼니싱 리소네이터를 사용해야 한다면 k+1번째 줄에 i와 j를 공백으로 구분하여 출력한다.

만약 퍼즐을 해결하는 방법이 여러 개라면 그 중 하나만 출력하면 된다.

루미너스가 퍼즐을 해결할 수 없으면 Run을 출력한다.

• 1 ≤ N,M ≤ 3,000
• 1 ≤ K ≤ 2,000,000
• 모든 퍼즐에서 NM의 합은 10,000,000을 넘지 않는다.

TMI : 안티 매직쉘은 치명적인 상태 이상을 무시하는 보호막을 생성하는 루미너스의 스킬이다.