Python で解いてTLEだったので，Go に移植．
最初，通ったものの1600 ms とぶっちぎりで遅かったので，
を見てプロファイリングしてみたら，どうやら読むとこと書くとこが遅いっぽかったので，
最後に書き出すところを strings.Join() してから fmt.Println() 一回でやるようにして 1100 ms，
標準入力から読むところを，fmt.Scan() で読んでいたのを，
を参考にして bufio の ReadLine() でやるようにして，最終的に250 ms ぐらいになった．
あまり Buffer size を大きくしすぎるとMLEになるので程よいサイズで．
