Mahjong Waiting Tiles

Given a 13 tile mahjong hand numbered 1 to 9, list every tile still available that completes the hand into one head plus four bodies, or into seven distinct heads.

Medium7BacktrackingRecursionImplementationBrute forceInterviewNo attempts yetTime limit1sMemory limit256 MB

Problem

Alex likes mahjong. He decided to write a program to practice it.

Mahjong is played with 136 tiles. Here the rules are simplified, and only 36 tiles are used: the 9 kinds of bamboo tiles (1 bam, 2 bam, 3 bam, 4 bam, 5 bam, 6 bam, 7 bam, 8 bam, 9 bam), 4 copies of each.

Mahjong has heads and bodies. A head is a set of 2 identical tiles. A body is a set of 3 tiles whose numbers are consecutive and differ by 1 from each other, or a set of 3 identical tiles. Here are examples of what is a head or a body and what is not.

  • (2 bam): only one tile, so it is neither a head nor a body.
  • (3 bam, 3 bam): 2 identical tiles, so this set is a head.
  • (7 bam, 8 bam, 9 bam): 7, 8, 9 are consecutive numbers, so this set is a body.
  • (1 bam, 3 bam, 5 bam): 1, 3, 5 are not consecutive numbers. They must differ by 1 from each other. So this set is not a body.
  • (8 bam, 9 bam, 1 bam): 1 bam does not come after 9 bam. The numbers cannot wrap around, so this set is not a body.
  • (9 bam, 9 bam, 9 bam): 3 identical tiles, so this set is a body.
  • (4 bam, 5 bam, 4 bam): 4, 4, 5 are not three consecutive numbers. So this set is not a body.
  • (8 bam, 8 bam, 8 bam, 8 bam): 4 tiles, so it is neither a head nor a body.

Pick 14 tiles out of the 36 and split them into 1 head and 4 bodies, or into 7 heads. All 14 tiles must belong to exactly one head or one body, and no tile may be left over. A hand split this way is complete. When splitting into 7 heads, two heads of the same kind are not allowed.

You hold 13 tiles. If you take one more tile from the remaining 23 tiles to make 14, and those 14 tiles are complete, the tile you took is a waiting tile. Alex is practicing how to find the waiting tiles of a 13 tile hand. Help Alex.

Input

The first line has the 13 tiles you hold, written as numbers from 1 to 9 and separated by spaces. The same number appears at most 4 times.

Output

Print every waiting tile in increasing order on one line, separated by spaces. If there is no waiting tile, print -1.

Hint

In the first example, taking 7 gives the head 55 and the bodies 111, 222, 789, 789. In the second example every tile from 1 to 9 is a waiting tile. In the third example, taking 2 gives the seven heads 11, 22, 33, 44, 66, 88, 99. In the fourth example, taking 5 gives the head 66 and the bodies 111, 555, 789, 789. In that same example, taking 1 gives the heads 11, 11, 55, 66, 77, 88, 99, and two heads of the same kind are present, so 1 is not a waiting tile. In the fifth example, taking 1 would split into the head 11 and the bodies 111, 234, 444, 888, but all 4 copies of 1 bam are already in hand, so no 1 bam is left among the other 23 tiles. So 1 is not a waiting tile.