Tag Discussion Solution Statistics Submit
 

UAPC 2012 (RUPC)
 

Transparent Mahjong

Time Limit : 3 sec, Memory Limit : 65536 KB

Transparent Mahjong

F: 透明な麻雀牌

あなたは,闇に舞い降りた天災と噂されるギャンブラーの鷹巣さんと麻雀で対局することになった. 鷹巣さんは天災と噂されるだけあって,鷹巣牌という奇怪な麻雀牌を用いた対局を提案してきた.

麻雀とは,プレイヤーが互いに手牌という複数枚の牌を持ち合い,自分の手牌を相手よりもはやく,アガリの形にすることで勝利が確定するゲームである. 麻雀の牌の表側には,その牌が何であるかが描かれており,牌の裏側には,何も描かれていない. よって,あなたが麻雀で対局するときは,あなたの手牌の表側をあなたの側に,裏側を対局者の側に向けるとよい. こうすることで,あなたの手牌が何であるかは,あなたのみが知ることができる. 麻雀の醍醐味は,プレイヤーが互の手配を読み合い,それを楽しむことにある.

しかしながら,鷹巣牌は透明な麻雀牌である. 鷹巣牌は透明であるため,プレイヤーは互いに相手の手牌を知ることができる. これでは,手配の読み合いを楽しむことができない.

「もはや,これは麻雀ではない.」と,鷹巣牌を用いることに納得できないあなたは,鷹巣さんとの紆余曲折を経た協議の結果,鷹巣牌と普通の麻雀牌を混ぜて対局することになった.

手始めに,あなたは,鷹巣さんの手牌のアガリ牌が何であるかを予想することにした. 鷹巣さんの手牌は,鷹巣牌と普通の牌から構成される. 問題の簡単のため,鷹巣牌と普通の牌は,1から12の12種類各4枚からなるものとする.

3n+2枚の牌からなる手牌について,次の3つの条件が満たされるとき,その手牌はアガリである.

  • 同じ数字を組み合わせた牌の組が1つ存在する
  • 残りの3n枚の牌は,3個の数字の組合せのnグループになる
  • それぞれのグループは,同じ数字を3つ組み合わせたものか,3つの連続する数字を組み合わせたものである

例えば,

1 1 1 3 3 3 5 5 5 7 7 7 8 9

のような14枚の牌は,全て鷹巣牌で構成されている. この場合,次のように2つの牌の組合せ1つと4つのグループを作ることができ,アガリである.

(1 1 1) (3 3 3) (5 5 5) (7 7) (7 8 9)

次に,普通の牌と鷹巣牌が混ざった手牌の例を挙げる.

1 1 1 3 3 3 5 5 5 7 7 7 * *

のような14枚の牌は,12枚の鷹巣牌と2枚の普通の牌(*)で構成されている. この場合,次のように2つの普通の牌が8と9であるかもしれないので,2つの牌の組合せ1つと4つのグループを作ることができ,アガリであるかもしれない.

(1 1 1) (3 3 3) (5 5 5) (7 7) (7 [8] [9])

同じ例について,次のように2つの普通の牌が8と8であるかもしれないので,以下のような形のアガリであるかもしれない.

(1 1 1) (3 3 3) (5 5 5) (7 7 7) ([8] [8])

しかし,7という同じ牌は4枚までしか使えないので,以下のような形のアガリであることはない.

(1 1 1) (3 3 3) (5 5 5) (7 7 7) ([7] [7])

鷹巣さんの3n+1枚の手牌が入力として与えられたときに, 鷹巣さんの手牌に1枚の牌を加えて,3n+2枚の手牌を作ることを考える. このときに,3n+2枚の手牌がアガリになり得るような加える1枚の牌(アガリ牌)を全て求めよ.

Input

入力は,次の形式で与えられる.

n
1 2 ... 3n+1

入力データは次の条件を満たす nは,0 <= n <= 15を満たす. 各牌は,鷹巣牌か普通の牌である.鷹巣牌の場合は,1以上12以下の整数で表され,普通の牌の場合は,文字*で表される.

Output

アガリ牌の一覧を昇順に出力せよ.アガリ牌を1つ出力する度に改行を出力せよ. あがり牌がない場合は,-1を1行に表示せよ.

Sample Input 1

4
1 1 1 3 3 3 5 5 5 7 7 7 9

Sample Output 1

8
9

Sample Input 2

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

Sample Output 2

1
4
7
9
10

Sample Input 3

4
1 1 1 4 4 4 7 7 7 8 8 9 *

Sample Output 3

6
7
8
9
10
11

Sample Input 4

4
1 * * * * * * * * * * * *

Sample Output 4

1
2
3
4
5
6
7
8
9
10
11
12

Sample Input 5

1
3 * 1 4

Sample Output 5

1
2
4
5

Source: Aizu Competitive Programming Camp 2012 , Day 1, Aizu-Wakamatsu, Japan, 2012-09-03
Problem Setter:  THE 2DM@STER(@Respect2D, @slip0110, @_shnyh) ,  @kioa341, @utisam