library(stringr)
 
lexi <- function(x) {
  opt <- vector(length = str_length(x))
  for(i in 1:str_length(x))
    opt[i] <- str_sub(x, i)
  sub <- order(opt)[1] - 1
  new <- str_c(opt[sub+1], str_sub(x, 1, sub), collapse = "")
  return(cat(sub, new, "\n"))
}
 
input <- "aabbccddbbaabb\nonion\nbbaaccaadd\nalfalfa\nweugweougewoiheew\npneumonoultramicroscopicsilicovolcanoconiosis"
input <- str_split(input, "\n")[[1]]
invisible(sapply(input, lexi))

bGlicmFyeShzdHJpbmdyKQoKbGV4aSA8LSBmdW5jdGlvbih4KSB7CiAgb3B0IDwtIHZlY3RvcihsZW5ndGggPSBzdHJfbGVuZ3RoKHgpKQogIGZvcihpIGluIDE6c3RyX2xlbmd0aCh4KSkKICAgIG9wdFtpXSA8LSBzdHJfc3ViKHgsIGkpCiAgc3ViIDwtIG9yZGVyKG9wdClbMV0gLSAxCiAgbmV3IDwtIHN0cl9jKG9wdFtzdWIrMV0sIHN0cl9zdWIoeCwgMSwgc3ViKSwgY29sbGFwc2UgPSAiIikKICByZXR1cm4oY2F0KHN1YiwgbmV3LCAiXG4iKSkKfQoKaW5wdXQgPC0gImFhYmJjY2RkYmJhYWJiXG5vbmlvblxuYmJhYWNjYWFkZFxuYWxmYWxmYVxud2V1Z3dlb3VnZXdvaWhlZXdcbnBuZXVtb25vdWx0cmFtaWNyb3Njb3BpY3NpbGljb3ZvbGNhbm9jb25pb3NpcyIKaW5wdXQgPC0gc3RyX3NwbGl0KGlucHV0LCAiXG4iKVtbMV1dCmludmlzaWJsZShzYXBwbHkoaW5wdXQsIGxleGkpKQ==