생존 신호

다오는 카트라이더 러쉬플러스에서 최고의 레이서다. 다오는 아이스리온 랜드의 설산 다운힐 코스로 하루를 시작하는데, 연습 카트로 한 바퀴를 도는데 $1$분이 채 걸리지 않는다 한다.

이번 시즌에 새로 나온 저스티스 바이크를 럭키 센터에서 뽑아 신난 다오는 이 바이크를 타고 붐힐 마을에서 빌리지 운명의 다리를 건너고 있었다. 하지만 기뻐서 너무 과속한 탓일까, 로봇 배찌 카트와 부딪친 다오는 하늘로 높이 떠올라 우주까지 날아가 버렸다.

우주를 떠돌던 다오는 충분히 많은 개수의 양면 거울과 큰 격자판 하나, 그리고 단 한 개의 레이저 포인터를 구할 수 있었다.

다오는 이 격자판에 양면 거울을 잘 배치한 후 레이저 포인터로 빛을 쏘아 크레이지 파크 세상에 생존 신호를 보내고자 한다 다오의 계획을 자세하게 설명하자면 이러하다.

먼저, 격자판의 크기는 $H \times W$이다.

각 격자 칸은 길이 $2$의 정사각형 모양이며, (1) 아무것도 없는 칸이거나 (2) 거울을 배치할 수 있는 칸, (3) 거울이 고정되어 있는 칸 혹은 (4) 사방이 암흑 벽으로 막힌 칸이다. 이미 고정되어 있는 거울은 위치나 방향을 바꿀 수 없다. 격자 칸에 거울을 배치할 때 거울은 그 격자 칸의 중심에 놓여야 하며, 수직 방향, 수평 방향 또는 $45$도의 사선 방향을 이루어야 한다.

격자판의 테두리는 암흑 벽으로 이루어져 있고, 몇 개의 작은 구멍이 뚫려 있다. 모든 구멍은 항상 어떤 격자 칸의 한 변의 중심에 위치한다.

다음 <그림 1>은 가능한 격자판의 상태 몇 가지를 보여준다.

양면 거울의 배치를 모두 마쳤다면 다오는 레이저 포인터로 빛을 쏘아 생존 신호를 보내야 한다. 이때, 빛은 수직 또는 수평 방향으로 테두리의 구멍을 통해 들어가고, 암흑 벽이나 거울 옆면과 만나지 않으면서, 양면 거울에 의해 반사되다가 다시 구멍을 통해 나와야 한다.

이렇게 만든 생존 신호의 세기를 격자판 내부에서 빛이 이동한 거리로 정의하자. 단, 빛이 왔던 경로를 되돌아가는 경우에는 그 거리의 절반으로 정의하자. 생존 신호의 세기를 계산할 때에는 거울의 두께를 무시해도 좋다.

다음 <그림 2>는 각 생존 신호의 세기를 보여준다.

다오는 큰 세기의 생존 신호를 만들어 얼른 우주에서 구출되기를 원한다. 지금도 다오와 디지니는 서로를 애타게 찾고 있다. NYPC 2021 예선이 끝나기 전에 연인이 서로 만날 수 있도록 다오와 함께 큰 세기의 생존 신호를 만들어보자!

입력 형식

첫 줄에 격자판의 크기를 나타내는 두 정수 $H$와 $W$가 공백으로 구분되어 주어진다. ($1 \le H \le 9$; $1 \le W \le 20$)

그 다음 $H$ 개의 줄에 각 격자 칸의 초기 상태를 나타내는 $W$ 개의 문자가 주어진다. 주어지는 문자는 ., ?, |, -, /, \, @ 중 하나이다. .와 ?는 각각 차례대로 아무것도 없는 칸과 거울을 배치할 수 있는 칸을 의미한다. |, -, /, \는 모두 거울이 고정되어 있는 칸을 의미하며, 그 거울의 방향은 문자의 방향과 동일하다. \의 방향은 왼쪽 위에서 오른쪽 아래로 내려가는 $45$도의 사선 방향임에 유의하라. @는 사방이 암흑 벽으로 막힌 칸을 의미한다.

그 다음 줄에 구멍의 개수를 나타내는 정수 $K$가 주어진다. ($1 \le K \le 2 \times (H+W)$)

그 다음 $K$ 개의 줄에 각 구멍의 $x$좌표와 $y$좌표가 공백으로 구분되어 주어진다. 격자판의 왼쪽 위 꼭짓점의 좌표는 $(0, 0)$, 오른쪽 아래 꼭짓점의 좌표는 $(2W, 2H)$이다.

출력 형식

첫 줄에 빛이 들어가는 구멍의 $x$좌표와 $y$좌표를 공백으로 구분하여 출력한다.

그 다음 $H$ 개의 줄에 걸쳐 양면 거울의 배치를 모두 마친 후의 격자판의 상태를 출력한다. 입력과 동일한 형식을 사용하되, 문자 ?는 사용하면 안된다.

예제

4 4
/.??
?@..
.|?.
?.\?
7
0 3
0 7
3 0
5 8
7 0
8 5
8 7

0 7
/..\
.@..
.|/.
/.\/

예제 설명

출력 예제가 나타내는 생존 신호는 <그림 3>과 같다.

이 문제는 생존 신호의 세기에 따라 점수가 주어지는 문제이다. 정확한 점수의 계산 공식은 아래의 "채점 방식"을 참고하라.

채점 방식

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

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

• $S$ : 미션의 만점
• $P$ : 미션에 대한 참가자의 점수
• $\alpha$, $\beta$ : 각 미션마다 정해진 상수
• $\alpha$ : 만점의 $60$%를 받을 수 있는 생존 신호의 세기의 최솟값
• $\beta$ : 만점을 받을 수 있는 생존 신호의 세기의 최솟값
• $L$ : 참가자의 출력에 따른 생존 신호의 세기

단, 참가자의 출력이 올바르지 않은 경우 (출력 형식을 맞추지 않았거나, 빛의 경로가 조건을 만족하지 않는 경우 등) $L = 0$ 이다.

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

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

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

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

문제 해결을 도와주는 시뮬레이터가 아래 미션에 대해 제공된다. 제공되는 시뮬레이터는 최신 버전의 크롬 브라우저에서 여는 것을 권장한다.

해설