#Include "ext/strings/strsplit.bi"

#Define _DUMP(x)    PRINT #x + " = " + Str(x)
#Define Boolean     INTEGER
#Define True        1
#Define False       0
#Define NULL        0

#Define QSORT_DATA_TYPE     Word

FUNCTION CalcValue(s AS STRING) AS ULongInt
    DIM k AS INTEGER
    DIM c AS STRING
    DIM sum AS uLongInt = 0
    DIM mul AS ULongInt

    FOR k = LEN(s) TO 1 STEP -1
        c = Mid(s,k,1)
        mul = 26 ^ (LEN(s) - k)
        sum += ASC(c)-97 * mul
    NEXT
    CalcValue = sum
END FUNCTION

TYPE Word
    Public:
        DECLARE Constructor()
        DECLARE Constructor(w AS Word)
        DECLARE Constructor(s AS STRING)
        Text AS STRING
        Index AS INTEGER
        DECLARE Operator LET (ByRef rhs AS Word)
        DECLARE SUB InitFrom(s AS STRING)
        DECLARE SUB SetCurrentLetter(idx AS INTEGER)
        DECLARE FUNCTION GetCharC(idx AS INTEGER) AS INTEGER
END TYPE

DECLARE Operator < (ByRef lhs AS Word,ByRef rhs AS Word) AS Boolean
DECLARE Operator > (ByRef lhs AS Word,ByRef rhs AS Word) AS Boolean
DECLARE Operator <= (ByRef lhs AS Word,ByRef rhs AS Word) AS Boolean
DECLARE Operator >= (ByRef lhs AS Word,ByRef rhs AS Word) AS Boolean
DECLARE Operator = (ByRef lhs AS Word,ByRef rhs AS Word) AS Boolean

Operator Word.LET (ByRef rhs AS Word)
    This.Index = rhs.Index
    This.Text = rhs.Text
END Operator

SUB Word.InitFrom(s AS STRING)
    This.Text = s
    This.Index = ASC(s)
END SUB

SUB Word.SetCurrentLetter(idx AS INTEGER)
    IF idx > LEN(This.Text) THEN
        This.Index = 255
    ELSE
        This.Index = ASC(Mid(This.Text,idx,1))
    EndIf

END SUB

FUNCTION Word.GetCharC(idx AS INTEGER) AS INTEGER
    IF idx > LEN(This.Text) THEN RETURN -1
    RETURN ASC(Mid(This.Text, idx, 1))
END FUNCTION

Constructor Word()
    This.Index = 0
    This.Text = ""
END Constructor

Constructor Word(w AS Word)
    This.Index = w.Index
    This.Text = w.Text
END Constructor

Constructor Word(s AS STRING)
    This.Text = s
    This.Index = ASC(s)
END Constructor

Operator < (ByRef lhs AS Word,ByRef rhs AS Word) AS Boolean
    RETURN IIf(lhs.Index < rhs.Index, TRUE, FALSE)
END Operator

Operator > (ByRef lhs AS Word,ByRef rhs AS Word) AS Boolean
    RETURN IIf(lhs.Index > rhs.Index, TRUE, FALSE)
END Operator

Operator <= (ByRef lhs AS Word,ByRef rhs AS Word) AS Boolean
    RETURN IIf(lhs.Index <= rhs.Index, TRUE, FALSE)
END Operator

Operator >= (ByRef lhs AS Word,ByRef rhs AS Word) AS Boolean
    RETURN IIf(lhs.Index >= rhs.Index, TRUE, FALSE)
END Operator

Operator = (ByRef lhs AS Word,ByRef rhs AS Word) AS Boolean
    RETURN IIf(lhs.Index = rhs.Index, TRUE, FALSE)
END Operator


SUB qsort OverLoad(A() AS QSORT_DATA_TYPE, L AS INTEGER, R AS INTEGER)

        IF L < R THEN
                DIM AS INTEGER i = L, j = R
                DIM AS QSORT_DATA_TYPE Pivot = A((L+R)*0.5)
                DO
                        WHILE A(i) < Pivot AND i < R: i += 1: WEND
                        WHILE A(j) > Pivot AND j > L: j -= 1: WEND
                        IF i <= j THEN SWAP A(i), A(j): i += 1: j -= 1
                LOOP WHILE i <= j
                IF L < j THEN qsort(A(), L, j)
                IF R > i THEN qsort(A(), i, R)
        END IF

END SUB

SUB qsort OverLoad(A() AS QSORT_DATA_TYPE)
    qsort(A(), LBOUND(A), UBOUND(A))
END SUB

SUB LexSort OverLoad(A() AS QSORT_DATA_TYPE, IdxStart AS INTEGER, IdxEnd AS INTEGER, Letter AS INTEGER)
    DIM k AS INTEGER
    DIM c AS INTEGER
    DIM groupStart AS INTEGER
    DIM groupEnd AS INTEGER


    FOR k = IdxStart TO IdxEnd
        a(k).SetCurrentLetter(Letter)
    NEXT

    qsort(a(), IdxStart, IdxEnd)
    groupStart = IdxStart
    groupEnd = groupStart

    FOR k = IdxStart TO IdxEnd
        IF a(k).getcharc(Letter) = c AND c > 0 THEN
            groupEnd += 1
        ELSEIF groupEnd > groupStart THEN
            ' sort things out
            'Print "Found group from "; groupStart; " to "; groupEnd
            'Print "recoursing.."
            LexSort(a(), groupStart, groupEnd, Letter+1)
            groupStart = k
            groupEnd = groupStart
        ELSE
            groupStart = k
            groupEnd = groupStart
        EndIf

        c = a(k).GetCharC(Letter)
    NEXT

    IF (groupEnd > groupStart) THEN
        'Print "Found group from "; groupStart; " to "; groupEnd
        'Print "recoursing.."
        LexSort(a(), groupStart, groupEnd, Letter+1)
    EndIf
END SUB

SUB LexSort OverLoad(A() AS QSORT_DATA_TYPE)
    LexSort(A(), LBOUND(A), UBOUND(A), 1)
END SUB


DIM ProblemCount AS INTEGER
DIM Problems() AS STRING
DIM Words() AS STRING
DIM SortableWords() AS Word
DIM WordCount AS INTEGER
DIM k AS INTEGER
DIM i AS INTEGER
DIM SolutionCount AS INTEGER

OPEN "input.txt" FOR INPUT AS 1

INPUT #1, ProblemCount

REDIM Problems(ProblemCount-1) AS STRING
DO WHILE NOT EOF(1) AND ProblemCount > k
    LINE INPUT #1, Problems(k)
    k += 1
LOOP
CLOSE 1

FOR k = 0 TO ProblemCount - 1
    '_DUMP(Problems(k))

    ext.strings.Split(Problems(k), Words(), " ", 2)
    WordCount = CINT(Words(0))
    ext.strings.Split(Mid(Problems(k), LEN(Words(0)) + 2), Words(), " ", WordCount)

    REDIM SortableWords(WordCount - 1) AS Word

    FOR i = 0 TO WordCount - 1
        '_DUMP(Words(i))
        SortableWords(i).InitFrom(Words(i))
    NEXT

    LexSort(SortableWords())

    FOR i = 0 TO WordCount - 1
        PRINT SortableWords(i).Text;
    NEXT
    PRINT
NEXT

END