[mappu]

If you have an unknown input size and a finite number of requested output lines, you can still do it in O(n) and no additional memory, by having a steadily-decreasing chance of replacing one of the outputs with the next line.