The input for this problem is fairly tedious to type out. So here's the sample input / output files: