시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 108 62 56 61.538%

문제

알렉스는 마작을 좋아한다. 그는 마작을 연습하기 위해서 프로그램을 만드려고 한다.

마작은 136개의 패를 가지고 하는 게임이다. 우리는 마작을 단순화 시켜서 삭수패 9종류(1삭, 2삭, 3삭, 4삭, 5삭, 6삭, 7삭, 8삭, 9삭)를 4개씩, 총 36개의 패만 가지고 프로그램을 만든다.

마작에는 머리와 몸통이라는 개념이 존재한다. 머리는 같은 패 2개의 조합을 말한다. 몸통은 연속된 패 3개 혹은 같은 패 3개의 조합을 말한다. 다음은 머리 혹은 몸통인 것과 그렇지 않은 것의 예를 나타낸다:

  • (2삭): 패가 하나이므로, 머리도 몸통도 될 수 없다.
  • (3삭, 3삭): 같은 패 2개가 있으므로, 이 두 패의 조합은 머리이다.
  • (7삭, 8삭, 9삭): 7, 8, 9는 연속된 수 이므로, 이 세 패의 조합은 몸통이다.
  • (1삭, 3삭, 5삭): 1, 3, 5는 연속된 수가 아니다. (서로 1씩 차이가 나야한다.) 그러므로, 이 세 패의 조합은 몸통이 아니다.
  • (8삭, 9삭, 1삭): 9삭과 1삭은 연속된 수가 아니다 (둥글게 이을 수 없다.)
  • (9삭, 9삭, 9삭): 같은 패 3개가 있으므로, 이 세 패의 조합은 몸통이다.
  • (4삭, 5삭, 4삭): 4, 4, 5는 연속된 세 수가 아니다. 그러므로, 이 세 패의 조합은 몸통이 아니다.
  • (8삭, 8삭, 8삭, 8삭): 패가 4개 이므로, 머리도 몸통도 될 수 없다. 

36개의 패 중 적당히 14개를 모아서, 머리 1개와 몸통 4개 혹은 머리 7개의 조합으로 만드려고 한다. 각 패는 반드시 하나의 머리나 하나의 몸통에 속해야 한다. 이를 패가 완성되었다고 한다. 단, 머리 7개를 모을 때, 같은 종류의 머리가 2개 있으면 안된다. 패 13개가 있을 때, 적당한 한 개의 패를 더 가져와서, 패를 14개로 만들어 완성시키려고 한다. 자기가 13개의 패가 있고, 남은 23개 중 어떤 패를 한 개 가져 왔을 때, 그 패가 완성될 수 있다면, 그것을 대기패 라고 한다. 그는 13개의 패가 있을때, 대기패를 찾는 법을 연습하고 있다. 알렉스를 도와주자!

입력

첫째 줄에는, 지금 가지고 있는 13개의 패가 1부터 9까지의 숫자로 공백으로 구분되어 들어온다.

출력

대기패를 오름차순으로 공백으로 구분하여 하나씩 출력하여라. 단, 대기패가 없다면, -1을 출력하여라.

예제 입력

1 1 1 2 2 2 5 5 7 8 8 9 9

예제 출력

7

예제 입력 2

1 1 1 2 3 4 5 6 7 8 9 9 9

예제 출력 2

1 2 3 4 5 6 7 8 9

예제 입력 3

1 1 2 3 3 4 4 6 6 8 8 9 9

예제 출력 3

2

예제 입력 4

1 1 1 5 5 6 6 7 7 8 8 9 9

예제 출력 4

5 6 8 9

예제 입력 5

1 1 1 1 2 3 4 4 4 4 8 8 8

예제 출력 5

-1

힌트

첫번째 예제에서는, 7이 들어오면, 머리가 55, 몸통이 111/222/789/789 형태로 완성 될 수 있다. 두번째 예제에서는, 모든 패가 대기패이다.  세번째 예제에서는, 2가 들어오면 머리가 11/22/33/44/66/88/99가 된다. 네번째 예제에서는, 5가 들어오면 머리가 66 몸통이 111/555/789/789가 된다. 1이 들어오면, 머리가 11/11/55/66/77/88/99 가 되는데, 같은 머리가 2개 있으므로 1은 대기패가 아니다. 다섯번째 예제에서는, 1이 들어오면 머리가 11, 몸통이 111/234/444/888 이 되지만, 남은 패 중에 1이 존재하지 않으므로(이미 4장을 사용하고 있으므로) 대기패가 아니다.