시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 38 10 7 35.000%

문제

홀수와 짝수는 오래된 소수 게임을 하면서 즐거운 시간을 보내고 있었어요.

이 게임은 임의의 자연수로 시작해요. 그 다음, 턴을 번갈아 가면서 1을 더하거나 소수로 나눌 수 있어요. 이 때, 결과는 항상 자연수이어야 해요. 1을 만드는 사람이 게임을 이기게 되요.

어느 화창한 날이었어요. 홀수와 짝수에게 새 친구 창영이가 생겼어요. 이제, 셋이서 게임을 하기 위해 게임의 규칙을 확장하려고 해요.

이제 게임을 이기면 점수를 얻어요. 각 사람이 얻는 점수는 게임을 하는 도중에 자신이 만든 가장 작은 숫자에요. 만약 자신의 턴이 돌아오지 않았는데 게임이 끝났다면, 시작한 숫자가 자신의 점수가 되요.

게임의 최종 승자는 각 게임에서 얻은 점수의 합이 가장 작은 사람이에요. 홀수와 짝수, 그리고 창영이는 싸우기 싫어요. 그래서 그들은 자신의 점수를 작게 만드는 것에만 초점을 맞추기로 했어요. 또, 같은 점수를 만들 수 있게 하는 수가 여러 개일 때, 그러한 숫자 중 가장 작은 수를 골라요.

턴은 항상 홀수 -> 짝수 -> 창영 -> ... 와 같은 식으로 진행되요. 하지만, 시작하는 사람은 바뀔 수도 있어요.

각 게임을 시작하는 사람과 그 사람이 가장 처음 고른 숫자가 입력으로 주어져요. 홀수, 짝수, 그리고 창영이가 게임을 항상 최적의 방법(optimal)로 진행할 때, 최종 점수를 구하는 프로그램을 작성해 보세요.

예를 들어, 짝수가 먼저 시작하고, 시작하는 숫자가 15라고 해요. 그럼 짝수는 16, 창영이는 8, 홀수는 4, 짝수는 2, 창영이는 1을 만들어요. 그럼 최종 점수는 홀수 4점, 짝수 2점, 창영 1점이 되요.

입력

첫째 줄에 홀수, 짝수, 그리고 창영이가 그날 밤에 진행한 게임의 수 n이 주어진다. (1 ≤ n ≤ 1000)

다음 n개 줄에는 각 게임을 시작한 사람과 시작한 숫자가 주어진다. 홀수가 먼저 시작한 경우에는 O, 짝수는 E, 창영이는 I로 주어지며, 시작한 숫자는 [1, 10000]에 포함된다. (시작 숫자가 1인 경우에는 모두 1점을 받게 된다)

출력

첫째 줄에 모든 게임을 하고 난 이후에 홀수, 짝수, 창영이의 최종 점수를 순서대로 출력한다.

예제 입력

3
O 13
I 14
E 15

예제 출력

6 29 16

예제 입력 2

1
O 4

예제 출력 2

2 1 4

힌트