Under construction

Still being built. Things may change

Two Mysterious Alphabets from a Tree

Interview

Time limit1sMemory limit128 MB

Summary
Find the max-sum root-to-leaf path in a number triangle, breaking ties by larger sum of squares, then print both sums and their mod-26 letters.
Level

Easy3 of 10

Topics
Dynamic programming
Solved
No attempts yet

Problem

A tree of height nn holds one integer in each node. Level kk (1≤k≤n1 \le k \le n) has kk nodes, and every node is joined to the two neighboring nodes on the level right below it. Those two nodes are its children. Nodes on level nn have no children, and a node inside a level can have two parents. The tree looks like this.

    1
   / \
  4   5
 / \ / \
7   8   9

Start at the root, step down to one of the children each time, and stop at the last level. Among the paths built this way, take the one whose node values add up to the largest total. In the picture that path is 1+5+9=151 + 5 + 9 = 15. Nodes that are not joined cannot be added together, so 5+75 + 7 is not a path.

The chosen path gives two numbers. The first number is the sum of the squares of the values on the path, and the second number is the sum of the values on the path. In the picture the first number is 12+52+92=1071^2 + 5^2 + 9^2 = 107 and the second number is 1+5+9=151 + 5 + 9 = 15.

When several paths tie for the largest total, take the one with the largest sum of squares among them.

Each of the two numbers becomes one lower case letter from 'a' to 'z'. 00 becomes 'a' and 2525 becomes 'z'. There are only 26 letters, so a number above 2525 uses the letter of its remainder modulo 26, which makes 00, 2626, and 5252 all 'a'. In the picture 107107 becomes 'd' and 1515 becomes 'p'.

Write a program that finds the two mysterious alphabets of a given tree.

Input

The first line contains the height nn of the tree (0<n<1000 < n < 100).

The second line contains the values of the tree separated by spaces, from level 1 to level nn, and left to right inside each level. Every value is an integer with 0<i<1000 < i < 100, and there are n(n+1)2\frac{n(n+1)}{2} of them.

Output

On the first line, print the two numbers from the rules above, the first number then the second number, separated by one space.

On the second line, print the two decoded letters in the same order with no space between them.

Examples4

  1. Example 1

    Input
    3
    1 4 5 7 8 9
    
    Expected output
    107 15
    dp
    
  2. Example 2

    Input
    4
    1 5 2 5 1 9 3 4 20 1
    
    Expected output
    486 32
    sg
    
  3. Example 3

    Input
    5
    2 4 9 1 3 1 1 1 1 2 12 5 4 3 2
    
    Expected output
    166 20
    ku
    
  4. Example 4

    Input
    6
    9 8 8 7 7 7 9 1 1 3 8 2 10 5 1 2 3 2 1 9 81
    
    Expected output
    6765 109
    ff