Adding subrectangles P88567

Given a grid with uppercase letters, compute the sum of the values of the letters in each rectangle with a corner in the upper-left extreme. The values of the letters are ’A’$=1$, ’B’$=1+2=3$, ’C’$=1+2+3=6$, ’D’$=1+2+3+4=10$, etcetera, up to ’Z’$=351$.

Input

Input consists of $0< r\leq 500$ lines, all of them with the same number of uppercase letters $0<c\leq 500$.

Output

Print $r$ lines with $c$ numbers each. The $j$-th number of the $i$-th row must be the sum of the values of the letters of the rectangle whose corners are the first letter of the input, and the $j$-th letter of the $i$-th row.

Hint

Consider using the inclusion-exclusion principle.