Under construction

Still being built. Things may change

Rummikub

Time limit1sMemory limit256 MB

Summary
From 14 tiles, find the highest scoring group or run, break ties by sorted tile order, and print it with its score.
Level

Medium4 of 10

Topics
Brute force, Sorting, Implementation
Solved
No attempts yet

Problem

Rummikub uses tiles numbered 1 to 13 in four colors, written here as A, B, C, and D. You hold 14 tiles and try to build groups and runs.

A group is 3 or 4 tiles that share a number and have all different colors. A run is 3 or more tiles of one color with consecutive numbers. The score of a combination is the sum of the numbers on its tiles.

Each tile is written as a color letter followed by a number from 1 to 13. A5, B5, C5 is a group, and A5, A6, A7 is a run.

A hand can contain the same tile more than once. A combination is built from distinct tiles, so duplicate copies do not count.

For each hand, decide whether any group or run exists, and if one does, find the combination with the highest score. When several combinations share the highest score, compare their sorted tile lists one tile at a time and take the smaller color letter, or the smaller number when the colors match. If one list is exactly the beginning of the other, take the shorter list.

For example, in A5 B5 C5 A6 A7 B13 A12 C1 C9 D1 D2 D3 D7 D12 the group A5 B5 C5 scores 15, the run A5 A6 A7 scores 18, and the run D1 D2 D3 scores 6, so the answer is A5 A6 A7 with 18 points.

Input

The first line contains the number of data sets TT. (1≤T≤1001 \le T \le 100)

Each of the next TT lines contains 14 tiles separated by spaces, in random order. Each tile is one of the letters A, B, C, D followed by an integer from 1 to 13.

Output

Print one line for each data set.

If no group and no run exists, print NO GROUPS OR RUNS. Otherwise print the tiles of the highest scoring combination, sorted by color letter and by number within one color, separated by spaces, then print the score of that combination at the end of the same line.

Examples3

  1. Example 1

    Input
    3
A5 B5 C5 A6 A7 B13 A12 C1 C9 D1 D2 D3 D7 D12
A1 A2 B1 B2 C5 C7 C9 C11 B6 B8 B10 B12 D3 D4
D13 C9 C13 A1 A3 A4 A5 A9 A13 B1 B2 B11 B12 B13
    Expected output
    A5 A6 A7 18
NO GROUPS OR RUNS
A13 B13 C13 D13 52

  2. Example 2

    Input
    1
A1 A3 A5 A7 B2 B4 B6 B8 C1 C3 C10 C12 D2 D5
    Expected output
    NO GROUPS OR RUNS

  3. Example 3

    Input
    1
A1 A2 A3 B1 B2 B3 C5 C7 C9 D4 D6 D8 D10 D12
    Expected output
    A1 A2 A3 6