#!/bin/sed -nf

	y/[A-Z]/[a-z]/

	# Autogenerate S table using a loop
	s/\(.*\)/\1%\1$aS bcdefghijklmnopqrstuvwxyz/
: loop_gen
	s/\([a-z]\)\(S*\) \(.\)/\1\2\3\2S /
	t loop_gen
	s/\(.*\)/\1:/

: loop_S
	s/\([^\n]\)\(.*%.*\)\1\(S*\)\(.*:.*\)/\2\1\3\4\1\3/
	t loop_S
	s/%\(.*\)$.*:/ \1/

: sort
	s/\([^S]\)\(S*\)\([^S]\)\(\2SS*\)/\3\4\1\2/
	t sort
	s/S//g
	# At this point we have:
	# sorted input
	H

# last line of input
$ {
	g
	s/\(.*\)/\1@/
	h
: main_loop
	s/@//
	s/^\n\([^\n]*\) \([^\n]*\)\(.*\)/\1 \2\3:\2/
: loop_end
	s/^\([^\n]*\) \([^\n]*\)\(.*\n\)\1 \([^\n]*\)\(.*\):\(.*\)/\1 \2\3\5:\6 \4/
	t loop_end
	s/.*://
	p
	g
	s/^\(\n[^\n]*\) \([^\n]*\)\(.*\)@/\3@\1 \2/
	h
/^@/ !{	t main_loop}

}
	d