2000 LSU Computer Science High School Programming Contest
Veteran Problem 10: Rare Order (Judge Copy)

MAIN
  Home
  Schedule
  Rules
  Compile

PROBLEMS
  Novice
  Veteran
  All

  

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Veteran Problem 10: Rare Order (Judge Copy)

A rare book collector recently discovered a book written in an unfamiliar language that used the same characters as the English language. The book contained a short index, but the ordering of the items in the index was different from what one would expect if the characters were ordered the same way as in the English alphabet. The collector tried to use the index to determine the ordering of characters (i.e., the collating sequence) of the strange alphabet, then gave up with frustration at the tedium of the task.

You are to write a program to complete the collector's work. In particular, your program will take a set of strings that has been sorted according to a particular collating sequence and determine what that sequence is.

Input

The input consists of an ordered list of strings of lowercase letters, one string per line. Each string contains at most 5 characters. The end of the list is signalled by a line with the single character `#'. No more than 10 lines will be in the list. Not all letters are necessarily used, but the list will imply a complete ordering among those letters that are used.

Output

Your output should be a single line containing lowercase letters in the order that specifies the collating sequence used to produce the input data file.

Sample Input

xwy
zx
zxy
zxw
ywwx
#

Sample Output

xzyw

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 0

xwy
zx
zxy
zxw
ywwx
#

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 0

xzyw

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 1

mmar
rmh
rma
rh
ha
#

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 1

mrha

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 2

a
b
c
d
#

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 2

abcd

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Test Data 3

zy
zxzx
zxzw
ywwz
#

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.

Output for Test Data 3

zyxw

Return to the Top of Page, 2000 Index Page, Novice Problem Set, or Veteran Problem Set.



The statements and opinions included in these pages are those of the LSU Computer Science High School Programming Contest Staff only. Any statements and opinions included in these pages are not those of Louisiana State University or the LSU Board of Supervisors.

© 2000 LSU Computer Science High School Programming Contest

This page last updated Fri Feb 11 21:55:29 2000.