#include <iostream>

#define max(a, b, c) max(a, max(b, c))

using namespace std;

int main() {

    int N, uS, dS, rS;

    cout << "Enter size of array: ";
    cin >> N;

    int arr[N][N], maxArr[N][N];

    cout << endl << "Enter array:" << endl;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
            maxArr[i][j] = arr[i][j];
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = N - 1; j >= 0; j--) {
            if (i != 0 || j != N - 1) {
                uS = dS = rS = -100;

                if (i - 1 >= 0) {
                    uS = maxArr[i - 1][j];
                }
                if (j + 1 < N) {
                    rS = maxArr[i][j + 1];
                }
                if (i - 1 >= 0 && j + 1 < N) {
                    dS = maxArr[i - 1][j + 1];
                }

                maxArr[i][j] += max(uS, rS, dS);
            }
        }
    }

    cout << endl << "Array after reverse:" << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << maxArr[i][j] << " ";
        }
        cout << endl;
    }

    cout << endl << "Way: " << endl;

    int x = N - 1, y = 0;

    while (x != 0 || y != N - 1) {
        uS = dS = rS = -100;

        if (x - 1 >= 0) {
            uS = maxArr[x - 1][y];
        }
        if (y + 1 < N) {
            rS = maxArr[x][y + 1];
        }
        if (x - 1 >= 0 && y + 1 < N) {
            dS = maxArr[x - 1][y + 1];
        }

        int maxS = max(uS, rS, dS);

        if (uS == maxS) {
            x--;
            cout << "Up ";
            continue;
        }
        if (rS == maxS) {
            y++;
            cout << "Right ";
            continue;
        }

        x--; y++;
        cout << "Diag ";
        continue;
    }

    cout << endl << endl << "Max = " << maxArr[N - 1][0] << endl;

    return 0;
}