This is a very tedious problem that requires complicated input parsing and output formatting; a reference solution is here.
