17369번 - 유령의 집

세상의 모든 지식을 깨우쳐 더 이상 공부할 것이 없게 된 승현이는 새로운 지식을 찾기 위해 프로그래밍 대회를 떠나지 못한 지박령들이 사는 유령의 집을 찾아갔다.

유령의 집의 예시

유령의 집은 정사각형 모양의 방들이 벽을 맞대고 붙어서 커다란 직사각형을 이루는 구조이며, 각 방에는 빛이 통과할 수 있는 창문이 사방의 벽에 하나씩 달려 있다. 바깥으로 뚫린 창문으로는 외부에서 안을 들여다볼 수 있다. 승현이는 이 창문들을 구분하기 위해 번호를 붙여 놓았다.

• 건물을 하늘에서 내려다봤을 때, 위쪽 벽에 난 창문들은 왼쪽부터 U1, U2, U3, ... 번, 아래쪽 벽에 난 창문들은 왼쪽부터 D1, D2, D3, ... 번으로 부른다.
• 마찬가지로 왼쪽 벽에 난 창문들은 위쪽부터 L1, L2, L3, ... 번, 오른쪽 벽에 난 창문들은 위쪽부터 R1, R2, R3, ... 번으로 부른다.

방들 중 몇몇에는 거울이 놓여 있거나 유령이 살고 있다. 거울은 방에 대각선 방향으로 놓여 있으며, 양면 모두 빛을 반사한다. 유령은 건너편이 훤히 비칠 정도로 투명하고, 모두 똑같이 생겨서 구별할 수 없다.

D2번 창문으로 들여다봤을 때

위의 예시와 같은 집에서 D2번 창문으로 안을 들여다보면 승현이에게서 1만큼 떨어진 위치와 4만큼 떨어진 위치에 유령이 한 마리씩 보인다. 승현이가 들여다본 창문들이 주어질 때, 승현이가 본 유령들의 수와 위치를 구해 보자.

첫 줄에 유령의 집의 세로 길이와 가로 길이를 의미하는 정수 N과 M, 거울 또는 유령이 있는 방의 개수를 의미하는 정수 K, 승현이가 안을 들여다본 횟수를 의미하는 정수 Q(1 ≤ N, M, K, Q ≤ 300,000)가 공백 하나를 사이에 두고 주어진다.

다음 K개의 줄에 걸쳐 각 줄에 방의 정보를 나타내는 정수 x와 y(1 ≤ x ≤ N, 1 ≤ y ≤ M), 문자 c가 공백 하나를 사이에 두고 주어진다. c는 /, \, ! 중 하나이며, x번째 줄 y번째 칸의 방에 c가 /이면 ╱ 방향 거울이, \이면 ╲ 방향 거울이, !이면 유령이 있음을 의미한다. 같은 위치의 방이 두 번 이상 주어지는 경우는 없다.

다음 Q개의 줄에 걸쳐 각 줄에 승현이가 들여다본 창문의 번호가 주어진다. 번호는 공백을 포함하지 않으며 해당 번호의 창문이 존재함이 보장된다.

Q개의 줄에 걸쳐 각 줄에 각 시도마다 승현이가 본 유령의 수와 각각의 유령이 승현이에게서 떨어져 있는 거리의 총합을 출력한다. 유령이 하나도 보이지 않을 경우 거리의 총합은 0이다.