描述

观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径，使路径经过的数字和最大。每一步可以走到左下方的点，也可以到达右下方的点。

        7 
      3   8 
    8   1   0 
  2   7   4   4 
4   5   2   6   5 
    

在上面的样例中，从 7 到 3 到 8 到 7 到 5 的路径产生了最大和。

格式

输入

第一行包含 R (1 ≤ R ≤ 1000)，表示行的数目。后面每行为这个数字金字塔特定行包含的整数。

所有给定的整数是非负的，且不大于 2000000。

输出

n 行，包含走过的点的纵、横坐标 (Y, X)。

第 n+1 行包含可能得到的最大的和。

示例

10
282843 
412905 1098313 
244406 302726 876540 
702602 661842 299031 42825 
784141 665692 192288 434737 180825 
514319 547710 995601 932582 1019152 833064 
138130 174138 932209 297036 715332 1134549 998768 
1010767 126702 323622 343793 958816 524590 794721 929157 
219494 264446 935275 1095137 313747 176818 585592 38527 771648 
817666 592971 801458 796763 651145 331761 819242 313343 831719 367013 

1 1
2 2
3 3
4 3
5 4
6 5
7 6
8 7
9 7
10 7
7344720

提示

如果有多条路径的最大和相同，输出最靠左的那一条路径。