물풍선 테스트

물풍선 아티스트 마리드는 새로운 물풍선을 개발해서 물풍선이 잘 동작하는지 테스트 하려고 한다.

물풍선 테스트는 $N \times N$모양의 격자에서 진행된다. 격자의 위에서 $x$번째 행, 왼쪽에서 $y$번째 열에 해당하는 격자 칸을 $(x, y)$라 쓰자. 격자 중 몇몇 격자 칸에는 가시가 설치되어 있어서, 해당 격자 칸에 물풍선을 놓는 것으로 물풍선을 테스트 할 수 있다. 가시가 없는 격자 칸에는 물풍선을 놓을 수 없다.

기존 물풍선이었던 R타입 물풍선은, 가로 세로 방향으로 물줄기를 발사할 수 있다. 다시 말해, 가시가 있는 격자 칸 $(x, y)$에 놓은 R타입 물풍선은 가로 방향으로 $(x, 1)$, $(x, 2)$, $\cdots$, $(x, N)$에 물줄기가 발사되고, 세로 방향으로 $(1, y)$, $(2, y)$, $\cdots$, $(N, y)$에 물줄기가 발사된다.

이번에 마리드가 개발한 새로운 물풍선은 Q타입 물풍선이고, 가로 세로 방향으로 물줄기를 발사하는 것에 더해 $45$도 대각선 방향으로도 물줄기를 발사할 수 있다. 다시 말해, $(x, y)$에 놓은 Q타입 물풍선은 가로 방향으로 $(x, 1)$, $(x, 2)$, $\cdots$, $(x, N)$에 물줄기가 발사되고, 세로 방향으로 $(1, y)$, $(2, y)$, $\cdots$, $(N, y)$에 물줄기가 발사되며, 왼쪽 위 방향 대각선 $\cdots$, $(x-2, y-2)$, $(x-1, y-1)$, $(x, y)$, $(x+1, y+1)$, $(x+2, y+2)$, $\cdots$와 오른쪽 위 방향 대각선 $\cdots$, $(x-2, y+2)$, $(x-1, y+1)$, $(x, y)$, $(x+1, y-1)$, $(x+2, y-2)$, $\cdots$에도 물줄기를 발사한다.

마리드는 R타입 물풍선을 $A$개 가지고 있으며, R타입 물풍선 하나당 $5$루찌의 가치가 있다. 또한, Q타입 물풍선을 $B$개 가지고 있으며, Q타입 물풍선 하나당 $9$루찌의 가치가 있다. 마리드는 테스트에 사용한 물풍선 가치의 합이 높도록 물풍선 테스트를 하고 싶다.

단, 물풍선을 테스트 할 때 조심해야 할 점은 어떤 물풍선의 물줄기가 발사되는 격자 칸에 다른 물풍선이 있으면 연쇄적인 물풍선 폭발이 일어날 수도 있어서 매우 위험해진다. 마리드는 이런 일이 일어나기를 원치 않는다.

마리드의 물풍선 테스트를 도와주자!

입력 형식

첫 줄에 격자의 가로와 세로 길이를 나타내는 정수 $N$, R타입 물풍선의 개수 $A$, Q타입 물풍선의 개수 $B$가 공백으로 구분되어 주어진다.

두 번째 줄 부터 다음 $N$개의 줄의 $i$번째 줄에는 .과 #으로 이루어진 길이 $N$의 문자열 $S_i$가 주어진다. 이 문자열의 $j$번째 문자가 . 이라는 것은 $(i, j)$에 가시가 설치되어 있어서 물풍선을 놓을 수 있다는 것을, # 이라는 것은 $(i, j)$에 가시가 설치되어 있지 않아서 물풍선을 놓을 수 없다는 것을 의미한다.

출력 형식

$N$개의 줄을 출력하고, $i$번째 줄에는 문자열 $T_i$를 출력한다.

여기서 문자열 $T_i$는 다음 조건을 만족하는 ., #, R 와 Q로 이루어진 길이가 $N$인 문자열이다.

• $T_i$의 $j$번째 문자가 . 인 경우 $(i, j)$에는 가시가 설치되어 있으며, 마리드는 이 격자 칸에 물풍선을 놓지 않았다.
• $T_i$의 $j$번째 문자가 # 인 경우 $(i, j)$에는 가시가 설치되어 있지 않다.
• $T_i$의 $j$번째 문자가 R 인 경우 $(i, j)$에는 가시가 설치되어 있으며, 마리드는 이 격자 칸에 R타입 물풍선을 놓았다.
• $T_i$의 $j$번째 문자가 Q 인 경우 $(i, j)$에는 가시가 설치되어 있으며, 마리드는 이 격자 칸에 Q타입 물풍선을 놓았다.

이때, 가시의 위치는 입력으로 주어진 위치와 동일해야 한다.

예제

4 4 1
#.#.
...#
#...
.#.#

#R#.
R..#
#.Q.
.#.#

예제 설명

이 출력에서 어떤 물풍선도 발사되는 물줄기가 다른 물풍선에 맞지 않는다. R 타입 물풍선을 $2$개, Q타입 물풍선을 $1$개 테스트 했으므로, 테스트한 물풍선 가치의 총합은 $19$이다.

이 문제는 테스트에 사용한 물풍선 가치의 합에 따라 점수가 주어지는 문제이다. 정확한 점수의 계산 공식은 아래의 "채점 방식"을 참고하라.

채점 방식

이 문제는 풀이 소스코드를 제출하지 않고, 각 미션의 입력데이터를 다운받아 알맞은 출력파일을 만들어 출력 파일만을 제출 하는 문제이다.

이 문제의 총점은 모든 미션의 점수의 합으로 계산된다. 각 미션의 점수를 계산하는 방법은 다음과 같다.

• $S$: 미션의 만점
• $P$: 미션에 대한 참가자의 점수
• $\alpha$, $\beta$: 각 미션마다 정해진 상수
  • $\alpha$: 만점의 $20\%$를 받을 수 있는 물풍선의 최소 가치 (루찌)
  • $\beta$: 만점을 받을 수 있는 물풍선의 최소 가치 (루찌)
• $L$: 참가자의 출력에 따른 물풍선 가치의 총합 (루찌)

단, 참가자의 출력이 올바르지 않은 경우 (출력 형식을 맞추지 않았거나, 어떤 물풍선의 발사되는 물줄기가 다른 물풍선에 맞은 경우) $L = 0$이다.

1. $L < \alpha$인 경우: $$P = S \times \left( \dfrac{1}{5} \times \dfrac{L}{\alpha} \right)$$
2. $\alpha \le L < \beta$인 경우: $$P = S \times \left( \dfrac{1}{5} + \dfrac{4}{5} \times \dfrac{L-\alpha}{\beta-\alpha} \right)$$
3. $\beta \le L$인 경우: $$P = S$$

이때, $P$는 최종적으로 $0.1$ 단위로 버림된다.

각 미션의 정보는 다음과 같다.

모든 미션의 입력 파일과 이미지 파일을 압축한 파일이 주어진다. 이미지 파일에서 가시가 설치되어 있어 물풍선을 놓을 수 있는 칸은 흰색, 가시가 설치되어 있지 않아 물픙선을 놓을 수 없는 칸은 검은색으로 표시되어 있다.

입력 및 이미지 파일 다운로드: 링크

각 미션마다 만점을 받을 수 있는 출력이 존재함이 보장된다.

해설