import Control.Monad.Trans.Writer.Strict

main = interact $ concat . map (unlines . execWriter . insertionSort . (map read) . words) . tail . lines

insertionSort xs = sorted [[], xs]

sorted [xs, []] = return [xs, []]
sorted [xs, (y:ys)] = (insert [xs, (y:ys)]) >>= sorted

insert [xs, (y:ys)] =
    let xs' = insertElem y xs
    in writer([xs', ys], [(unwords . map show) $ concat [xs', ys]])

insertElem :: Int -> [Int] -> [Int]
insertElem x [] = [x]
insertElem x (y:ys) = if (x < y) then (x:(y:ys)) else (y : (insertElem x ys))