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

빛과 어둠의 마법사 루미너스는 모험을 떠나고 있다. 하지만 지금 그는 함정이 가득한 미궁에 갇혀 있다. 빠르게 탈출하려고 지름길에 들어섰는데, 그 순간 퍼즐 게임이라는 함정 밭과 마주쳤다.

그는 빨리 탈출해야 할 이유가 있었고, 퍼즐 게임을 풀려고 함정 밭 앞으로 갔다. 그때 큰 소리와 함께 홀로그램이 생겼다. 홀로그램에는 줄어드는 타이머와 함께 "너의 스킬은 한 가지를 제외하고 모두 봉인되었다"라는 메시지가 쓰여 있었다. 루미너스가 급하게 "안티 매직쉘!"이라고 외쳐 보았지만 공허한 외침이 될 뿐이었다. 결국 그는 퍼즐을 풀지, 지름길을 포기할지 선택해야 했다.

퍼즐 게임은 $N \times M$ 격자판에서 진행된다. 각 칸에는 빛의 함정 또는 어둠의 함정이 있다. 안전하게 지나가려면 스킬을 써서 격자판의 모든 함정을 제거해야 한다.

루미너스가 봉인되지 않은 유일한 스킬은 빛의 퍼니싱 리소네이터이다. 이 스킬은 어둠의 함정에만 쓸 수 있다. 스킬을 쓰면 대상이 된 어둠의 함정은 제거되고, 그 칸과 상하좌우로 인접한 칸의 함정은 속성이 뒤집힌다.

미궁에는 함정이 끝없이 있어서, 이런 퍼즐을 총 $K$개 풀어야 한다.

각 퍼즐의 상태가 주어졌을 때, 루미너스가 각 퍼즐을 해결할 수 있는지 판단하고, 해결할 수 있다면 방법을 알려주자.

입력은 여러 개의 퍼즐로 이루어진다. 첫째 줄에 풀어야 할 퍼즐의 개수 $K$가 주어진다. 그 뒤로 각 퍼즐의 상태가 차례대로 주어진다.

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

이어서 $N$개의 줄에 L과 D로 이루어진 길이 $M$의 문자열이 주어진다. $i+1$번째 줄의 $j$번째 글자가 L이면 격자판의 $i$행 $j$열에 빛의 함정이 있다는 뜻이고, D이면 어둠의 함정이 있다는 뜻이다.

각 퍼즐에 대해 해결 가능 여부를 출력하고, 해결할 수 있다면 퍼즐을 푸는 방법도 출력한다.

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

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

방법이 여러 개라면 그중 하나만 출력하면 된다.

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

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