import List
main=interact(\x->sort[(9!read y,y++"\n")|y<-lines x]>>=snd)
x!y|y<2=x|odd y=y-x^9;x+1!y=x!div y 2