미니 지뢰찾기

인터넷에 연결되지 않은 컴퓨터를 사용해 본 사람이라면 대부분 지뢰찾기를 해 보았을 것이다. 지뢰찾기는 처음에는 내용이 알려지지 않은 RxC개의 칸으로 이루어진 직사각형 게임판에서 진행한다. 플레이어는 칸을 클릭하여 그 내용을 확인할 수 있다. 일부 칸에는 지뢰가 놓여 있으며, 플레이어가 그런 칸을 클릭하면 게임이 끝난다. 지뢰가 없는 각 칸에는 그 주변, 즉 변이나 꼭짓점을 공유하는 칸들에 지뢰가 몇 개 있는지를 나타내는 숫자가 대신 적혀 있다. 이 숫자들을 이용해 지뢰가 어디에 있는지 알아내고 지뢰를 피하는 것이 목적이다.

Rudolf는 프로 지뢰찾기 플레이어가 되기로 결심했다. 하지만 이전에 지뢰찾기를 해 본 적이 없어서, 크기가 2xN인 게임판에서 진행하는 더 쉬운 버전인 미니 지뢰찾기를 해 보려 한다. 또한 그는 수수께끼의 버그를 이용해 게임판 아래쪽 절반에 있는 모든 칸의 내용을 밝혀낼 수 있는 MinesweeperHaXX3000도 내려받았다. 그래도 Rudolf는 완전히 안심할 수 없어, 자신이 얻은 정보가 주어졌을 때 어떤 칸을 안전하게 클릭할 수 있는지 판별하는 프로그램을 작성해 달라고 부탁했다.

점수

여러 테스트 케이스 그룹으로 여러분의 풀이를 테스트한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$40$| $1 \leq N \leq 10000$이고 아래쪽 행에는 지뢰가 하나도 없다.

$2$ |$60$| 추가 제한이 없다.

첫 번째이자 유일한 줄에 길이가 $N$인 문자열이 주어진다 ($1 \leq N \leq 50000$). 이 문자열은 게임판의 아래쪽 절반을 나타내며, 각 문자는 지뢰를 뜻하는 'X'이거나, 해당 칸의 주변에 지뢰가 $d$개 있음을 나타내는 정수 $d$, $0 \leq d \leq 5$ 중 하나이다.

입력과 호환되는 유효한 게임판이 없다면 프로그램은 한 줄에 'fel'를 출력해야 한다(소문자임에 유의하라). 그렇지 않다면 게임판의 위쪽 절반에 있는 칸들을 나타내는 $N$개의 문자, 즉 'S', 'O', 'X'로 이루어진 문자열을 출력한다. 어떤 칸에 지뢰가 있을 수 없다면 그 칸을 'S'로, 그 칸에 지뢰가 있는 것이 확실하다면 'X'로, 그 칸에 지뢰가 있을 수도 있지만 반드시 있어야 하는 것은 아니라면 'O'(대문자 'o')로 나타낸다. 마지막 경우는 그 칸에 지뢰가 있는 유효한 게임판이 적어도 하나 있고, 그 칸에 지뢰가 없는 유효한 게임판도 적어도 하나 있다는 뜻이다. 자세한 설명은 그림을 참고하라.

첫 번째 예제 테스트 케이스에서 가능한 한 해를 나타낸 그림.

첫 번째 예제 테스트 케이스에서 가능한 또 다른 해를 나타낸 그림.