Slots of Fun

Time limit1sMemory limit128 MB

Summary
Given letters on a triangular lattice, find every letter whose three positions form an equilateral triangle.
Level

Medium6 of 10

Topics
Geometry, Brute force, Implementation, Math
Solved
No attempts yet

Problem

A slot machine has a display built from identical circles packed into a triangle. The top row holds one circle, and every row below it holds one more circle than the row above, so a display with nn rows has n(n+1)/2n(n+1)/2 circles. The circles are packed tightly, so the centers of neighbouring circles are all the same distance apart and their centers form a triangular lattice.

Each time the player pulls the lever, the machine writes a random lowercase letter into every circle. The machine pays off whenever three circles that hold the same letter sit at the vertices of an equilateral triangle (distances are measured between circle centers). To keep payoffs rare, the machine never prints more than three copies of any single letter in one display.

The manufacturer builds these machines with different numbers of rows and needs a program that finds the winning letters. Given a filled-in display, report every letter whose circles form an equilateral triangle.

Input

The input contains several displays. Each display starts with a line containing a single integer nn (1≤n≤121 \le n \le 12), the number of rows. The next line contains exactly n(n+1)/2n(n+1)/2 lowercase letters with no spaces: the contents of the circles listed row by row from the top row down, and left to right within each row. The input ends with a line containing a single 00, which is not a display and must not be processed.

Output

For each display, print one line listing every letter that forms an equilateral triangle, in alphabetical order and with no spaces between them. If no letter forms an equilateral triangle, print LOOOOOOOOSER! on that line instead.

Examples4

  1. Example 1

    Input
    4
    abccddadca
    6
    azdefccrhijrrmznzocpq
    2
    abc
    0
    
    Expected output
    ac
    crz
    LOOOOOOOOSER!
    
  2. Example 2

    Input
    2
    aaa
    0
    
    Expected output
    a
    
  3. Example 3

    Input
    1
    a
    0
    
    Expected output
    LOOOOOOOOSER!
    
  4. Example 4

    Input
    3
    abcada
    0
    
    Expected output
    a