바둑 끝내기

바둑은 격자판 위에서 하는 보드게임으로, 자기 색 돌로 최대한 넓은 집(영역)을 둘러싸는 것이 목표이다. 바둑 한 판을 온전히 두는 것은 컴퓨터에게 매우 어렵지만, 집의 경계가 거의 확정되어 마지막 몇 집만을 다투는 끝내기(endgame) 단계는 단순화한 모형으로 다룰 수 있다. 이 문제는 그러한 단순화된 끝내기 모형을 다룬다.

게임은 Alice와 Bob이 번갈아 두며 진행한다. 현재 Alice는 $a$ 집, Bob은 $b$ 집을 가지고 있다. 서로 영향을 주지 않는 $n$개의 독립된 구역이 있으며, 한 구역에서의 착수는 다른 어떤 구역에도 전혀 영향을 주지 않는다. 지금은 Alice의 차례이다.

진행 방식은 다음과 같다. 차례인 사람이 한 구역을 골라 그곳에 두면 상대가 같은 구역에서 응수하고, 그 구역이 정리될(settled) 때까지 서로 응수를 주고받는다. 구역이 정리된 뒤 차례인 사람이 다음 구역을 골라 같은 방식으로 두며, 모든 구역이 정리될 때까지 반복한다.

어떤 구역을 먼저 두는 쪽이 그 구역에서 유리하여 대개 더 많은 집을 얻는다. 이를 구역마다 다음과 같이 모형화한다. Alice가 구역 $i$를 먼저 두면 Alice는 $a_i$ 집을 얻고 Bob은 그 구역에서 아무것도 얻지 못한다. 반대로 Bob이 구역 $i$를 먼저 두면 Bob이 $b_i$ 집을 얻고 Alice는 얻지 못한다.

또한 구역은 어떤 사람에게 선수(sente) 일 수 있다. 어떤 구역이 그 구역을 먼저 둔 사람에게 선수이면, 그 구역이 정리된 뒤에도 여전히 그 사람의 차례가 되어 다음 구역을 고르게 된다. 먼저 둔 사람에게 선수가 아니라면, 그 구역이 정리된 뒤에는 상대의 차례가 된다. 한 구역은 두 사람 모두에게 선수일 수도, 한 사람에게만 선수일 수도, 아무에게도 선수가 아닐 수도 있다.

모든 구역의 정보가 주어질 때, 두 사람이 모두 최적으로 둔다고 가정하고 최종 점수를 구하라. 각 사람은 자신의 점수가 상대보다 가능한 한 많이 앞서기(또는 가능한 한 적게 뒤지기)를 원하며, 점수 차가 같은 결과들 중에서는 자신의 점수가 가장 큰 결과를 선호한다.

입력은 여러 개의 인스턴스로 이루어지며, 인스턴스들은 하나의 빈 줄로 구분된다.

각 인스턴스의 첫 줄에는 세 정수 $a$, $b$, $n$이 주어진다 ($0 \le a, b$, $a + b \le 361$, $0 \le n \le 361$). 각각 Alice의 현재 점수, Bob의 현재 점수, 아직 정리되지 않은 구역의 수이다.

이어지는 $n$개의 줄이 각 구역을 설명한다. 그중 $i$번째 줄에는 두 정수 $a_i$, $b_i$ ($0 \le a_i, b_i$, $1 \le a_i + b_i \le 361$)와 두 문자 $s_i$, $t_i$가 공백으로 구분되어 주어진다. $a_i$와 $b_i$는 각각 Alice와 Bob이 그 구역을 먼저 두어 얻는 집 수이다. 문자 $s_i$는 그 구역이 Alice에게 선수이면 S, 아니면 G이다. 마찬가지로 $t_i$는 그 구역이 Bob에게 선수이면 S, 아니면 G이다.

입력의 끝까지 인스턴스를 처리한다.

각 인스턴스마다 한 줄에 두 정수 $A$와 $B$를 공백으로 구분하여 출력한다. 이는 Alice가 처음 차례일 때 두 사람이 최적으로 둔 뒤의 Alice와 Bob의 최종 점수이다. 모든 인스턴스에서 $A + B \le 361$이다.