У табели димензија \(n \times n\) поља су попуњена цифрама од 0 до 9. Играч који се налази у горњем левом углу табеле може да у једном кораку пређе у суседно десно поље или суседно доње поље. Циљ му је да стигне до доњег десног поља тако да збир вредности на пређеним пољима буде максималан. Написати пpограм којим се одређује максимални збир коју може остварити играч при кретању од горњег левог до доњег десног угла и инструкције кретања: desno, dole, којима се обезбеђује кретање преко поља која дају максимални збир (ако има више могућих путева, исписати било који).

Улаз

У првој линији стандардног улаза се уноси број редова табеле \(n\) (\(1 \le n \le 30\)), а у следећих \(n\) редова по \(n\) цифара од 0 до 9.

Излаз

У првој линији стандардног излаза приказати тражену вредност максималног збира, а у наредним линијама исписати инструкције за кретање: desno, dole - у сваком реду по једну, којима се обезбеђује кретање преко поља која дају максимални збир.

Пример

Улаз

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

Излаз

38
desno
dole
dole
dole
dole
desno
desno
desno