왕들의 군주

위험한 해외 국가들과의 길고 지친 전쟁 끝에, 우리 나라는 마침내 거의 모든 적대 세력을 물리치고 승리를 거두었다. 이 영광스러운 승리는 앞으로 여러 해 동안 기억되고 기념될 것이다. 그리하여 우리 왕은 승전일을 공휴일로 선포하고, 이날 승전 기념 퍼레이드를 열기로 했다. 퍼레이드에서 왕은 군대와 함께 자신의 궁전에서 출발하여 나라의 모든 도시를 차례로 방문한다.

왕과 수행단은 친환경 전기 헬리콥터를 타고 이동하는데, 이 헬리콥터는 작동 반경이 비교적 짧다는 단점이 있다. 왕은 당신과 참모들에게 일부 농지와 모든 도시에 헬리콥터 착륙장을 건설하여, 각 도시가 착륙장 사이의 짧은 비행을 여러 번 거쳐 궁전에서 도달 가능하도록 만들라고 요청했다. 그러나 착륙장과 지원 인프라를 건설하는 데는 비용이 많이 든다. 따라서 착륙장을 건설하는 농지 타일의 수를 최소화하는 것이 중요하다.

또한 헬리콥터의 특수한 설계 때문에 왕과 군대는 특별한 방식으로 이동해야 하며, 이는 착륙장의 수와 위치에 영향을 줄 수 있다.

나라의 직사각형 격자 지도가 주어지며, 이 지도는 농지 타일, 도시 타일, 그리고 왕의 궁전 타일로 이루어져 있다. 또한 헬리콥터의 이동 방식도 주어진다. 헬리콥터는 체스에서 룩, 퀸, 비숍, 나이트, 또는 킹처럼 이동할 수 있다(이동 방식은 그림을 참고). 당신의 임무는 위에서 명시한 조건을 만족시키기 위해 착륙장을 설치해야 하는 농지 타일과 도시 타일의 최소 수를 구하는 것이다. 왕의 궁전 타일에는 이미 착륙장이 있으므로 새로 설치할 필요가 없다.

그림 1: 헬리콥터의 각 이동 방식 예시.

입력의 첫째 줄에는 두 정수 N과 M(1 ≤ N, M ≤ 15)이 주어지며, N은 우리 나라를 나타내는 격자의 행 수, M은 열 수이다. 둘째 줄에는 두 정수 X와 Y(1 ≤ X ≤ N, 1 ≤ Y ≤ M)가 주어지며, 이는 왕의 궁전 위치를 나타내고, 이어서 이동 방식을 결정하는 문자 하나가 주어진다("R"은 룩, "Q"는 퀸, "B"는 비숍, "N"은 나이트, "K"는 킹). 셋째 줄에는 정수 T(1 ≤ T ≤ 10)가 주어지며, 이는 나라의 도시 수이다. 그다음 T개의 줄이 이어지며, 각 줄에는 두 정수 W와 Z(1 ≤ W ≤ N, 1 ≤ Z ≤ M)가 주어진다. 각 줄은 도시 타일 하나의 위치를 나타낸다. 모든 도시는 서로 다른 타일을 차지하며, 어떤 도시도 궁전 타일을 차지하지 않는다. 도시나 궁전이 아닌 모든 타일은 농지로 간주한다.

착륙장을 설치할 농지 및 도시 타일의 최소 수를 나타내는 정수 하나를 출력한다. 왕과 군대가 모든 도시를 방문하는 것이 불가능하면 −1을 출력한다.