#include <cassert>
#include <iostream>

// The Ackermann function is famous for growing
// extraordinarily quickly.
//
// Its inverse, called the inverse Ackermann
// function, appears in the analysis of a particularly
// efficient implementation of a data structure
// called a disjoint set, or union-find.
//
// The inverse Ackermann function grows extraordinarily
// slowly. We will not study that analysis here, but
// first we will look at the function whose inverse
// appears in that analysis.
//
// There are several related definitions called the
// Ackermann function. We will use the following
// two-argument version:
//
//         A(0, n) = n + 1
//
//     A(m + 1, 0) = A(m, 1)
//
// A(m + 1, n + 1) = A(m, A(m + 1, n))
//
// for non-negative integers m and n.
//
// We will also define the single-argument function:
//
//     A(n) = A(n, n).
//
// Implement these functions.
//
// References:
//     https://en.wikipedia.org/wiki/Ackermann_function

// Function declarations
int main();

unsigned long long Ackermann(
    unsigned int const n
);

unsigned long long Ackermann(
    unsigned int const m,
    unsigned long long const n
);

// Function definitions
int main() {
    // First examine:
    //
    //     A(n) = A(n, n).
    //
    // Do NOT increase the upper bound without first
    // thinking about what A(4, 4) might mean.

    for ( unsigned int n{ 0 }; n <= 3; ++n ) {
        std::cout << "A(" << n << ") = "
                  << Ackermann( n )
                  << std::endl;
    }

    std::cout << std::endl;


    // Now examine the two-argument Ackermann
    // function for small values of m and n.

    for ( unsigned int m{ 0 }; m <= 3; ++m ) {
        for ( unsigned long long n{ 0 };
              n <= 6;
              ++n ) {
            std::cout << Ackermann( m, n )
                      << "\t";
        }

        std::cout << std::endl;
    }


    // Be VERY careful about experimenting with
    // larger values.
    //
    // We will see below that:
    //
    //     A(4, 0) = 13
    //
    // and:
    //
    //     A(4, 1) = 65533.
    //
    // Even though 65533 fits comfortably in an
    // unsigned long long, the straightforward
    // recursive calculation requires an enormous
    // number of recursive calls.
    //
    // The next value is:
    //
    //     A(4, 2) = 2^65536 - 3.
    //
    // This number has 19729 decimal digits.
    //
    // It cannot possibly be represented by an
    // unsigned long long.
    //
    // More importantly, attempting to calculate it
    // using the straightforward recursive function
    // below is completely impractical.
    //
    // Consequently, the following experiment is
    // intentionally commented out.
    //
    // std::cout << Ackermann( 4, 0 ) << std::endl;
    // std::cout << Ackermann( 4, 1 ) << std::endl;

    return 0;
}

unsigned long long Ackermann(
    unsigned int const n
) {
    // Your implementation here.

    return 1;
}

unsigned long long Ackermann(
    unsigned int const m,
    unsigned long long const n
) {
    // Your implementation here.

    return 1;
}














































// Hint
//
// The definition:
//
//         A(0, n) = n + 1
//
//     A(m + 1, 0) = A(m, 1)
//
// A(m + 1, n + 1) = A(m, A(m + 1, n))
//
// is mathematically elegant, but it is not quite
// in the form we want for a C++ function whose
// parameters are m and n.
//
// Rewrite it as:
//
//             /
//            (   n + 1                         m = 0
//             )
//   A(m,n) = <   A(m - 1, 1)                   n = 0
//             )
//            (   A(m - 1, A(m, n - 1))         otherwise.
//             \
//
// Notice something unusual about the final case.
//
// Most of the recursive functions we have written
// so far contain recursive calls such as:
//
//     f(n - 1)
//
// or:
//
//     f(n/2).
//
// Here we have:
//
//     A(m - 1, A(m, n - 1)).
//
// The result of one recursive call becomes an
// ARGUMENT to another recursive call.
//
// This is nested recursion.














































// Solution

/*
unsigned long long Ackermann(
    unsigned int const n
) {
    return Ackermann( n, n );
}

unsigned long long Ackermann(
    unsigned int const m,
    unsigned long long const n
) {
    if ( m == 0 ) {
        return n + 1;
    } else if ( n == 0 ) {
        return Ackermann( m - 1, 1 );
    } else {
        return Ackermann(
            m - 1,
            Ackermann( m, n - 1 )
        );
    }
}
*/














































// Understanding the first few cases
//
// At first glance, the definition:
//
//             /
//            (   n + 1                         m = 0
//             )
//   A(m,n) = <   A(m - 1, 1)                   n = 0
//             )
//            (   A(m - 1, A(m, n - 1))         otherwise
//             \
//
// may look almost incomprehensible.
//
// The easiest way to understand it is to fix m and
// determine what function of n we obtain.
//
//
//
// Case 1: m = 0
//
// This one is given directly:
//
//     A(0, n) = n + 1.
//
// Therefore:
//
//     A(0, 0) = 1
//     A(0, 1) = 2
//     A(0, 2) = 3
//     A(0, 3) = 4
//     A(0, 4) = 5
//
// and so on.
//
//
//
// Case 2: m = 1
//
// First:
//
//     A(1, 0)
//
//       = A(0, 1)
//
//       = 2.
//
// For n > 0:
//
//     A(1, n)
//
//       = A(0, A(1, n - 1)).
//
// But:
//
//     A(0, x) = x + 1.
//
// Therefore:
//
//     A(1, n)
//
//       = A(1, n - 1) + 1.
//
// Thus:
//
//     A(1, n) = n + 2.
//
// For example:
//
//     A(1, 0) = 2
//     A(1, 1) = 3
//     A(1, 2) = 4
//     A(1, 3) = 5
//     A(1, 4) = 6.
//
//
//
// Case 3: m = 2
//
// First:
//
//     A(2, 0)
//
//       = A(1, 1)
//
//       = 3.
//
// Then:
//
//     A(2, n)
//
//       = A(1, A(2, n - 1)).
//
// Since:
//
//     A(1, x) = x + 2,
//
// we have:
//
//     A(2, n)
//
//       = A(2, n - 1) + 2.
//
// Therefore:
//
//     A(2, n) = 2*n + 3.
//
// For example:
//
//     A(2, 0) =  3
//     A(2, 1) =  5
//     A(2, 2) =  7
//     A(2, 3) =  9
//     A(2, 4) = 11.
//
//
//
// Case 4: m = 3
//
// First:
//
//     A(3, 0)
//
//       = A(2, 1)
//
//       = 5.
//
// Then:
//
//     A(3, n)
//
//       = A(2, A(3, n - 1)).
//
// Since:
//
//     A(2, x) = 2*x + 3,
//
// we obtain:
//
//     A(3, n)
//
//       = 2*A(3, n - 1) + 3.
//
// This produces:
//
//     A(3, 0) =   5
//     A(3, 1) =  13
//     A(3, 2) =  29
//     A(3, 3) =  61
//     A(3, 4) = 125
//     A(3, 5) = 253
//     A(3, 6) = 509.
//
// The formula is:
//
//     A(3, n) = 2^(n + 3) - 3.
//
//
//
// Thus, the first few rows look like:
//
//        n       0      1      2      3      4
//
//     m = 0      1      2      3      4      5
//
//     m = 1      2      3      4      5      6
//
//     m = 2      3      5      7      9     11
//
//     m = 3      5     13     29     61    125
//
//
//
// Look at how the growth changes.
//
// For m = 0:
//
//     A(0, n) = n + 1
//
// which grows linearly.
//
//
// For m = 1:
//
//     A(1, n) = n + 2
//
// which also grows linearly.
//
//
// For m = 2:
//
//     A(2, n) = 2*n + 3
//
// which still grows linearly.
//
//
// But for m = 3:
//
//     A(3, n) = 2^(n + 3) - 3
//
// which grows exponentially.
//
//
//
// Then we reach m = 4.
//
// First:
//
//     A(4, 0)
//
//       = A(3, 1)
//
//       = 13.
//
// Next:
//
//     A(4, 1)
//
//       = A(3, A(4, 0))
//
//       = A(3, 13)
//
//       = 2^(13 + 3) - 3
//
//       = 2^16 - 3
//
//       = 65533.
//
// So:
//
//     A(4, 0) = 13
//
// but:
//
//     A(4, 1) = 65533.
//
//
//
// What about A(4, 2)?
//
// By definition:
//
//     A(4, 2)
//
//       = A(3, A(4, 1))
//
//       = A(3, 65533)
//
//       = 2^(65533 + 3) - 3
//
//       = 2^65536 - 3.
//
// This number has:
//
//     19729
//
// decimal digits.
//
//
//
// At this point, writing out the answer is already
// unreasonable.
//
// But this is only:
//
//     A(4, 2).
//
// The function has barely started.
//
//
//
// Why is this interesting?
//
// The Ackermann function is a classic example of a
// computable function that grows extraordinarily
// quickly.
//
// The definition itself contains only:
//
//     addition,
//     subtraction,
//     comparisons,
//     and recursion.
//
// Yet nested recursion causes the values to explode.
//
//
//
// There is an important programming lesson here.
//
// A mathematically correct recursive definition:
//
//     does NOT imply
//
// that directly translating the definition into
// recursive C++ code produces a practical algorithm.
//
// Our implementation:
//
//     return Ackermann(
//         m - 1,
//         Ackermann( m, n - 1 )
//     );
//
// is an almost literal translation of the
// mathematical definition.
//
// It is elegant.
//
// It is correct.
//
// It is also spectacularly impractical for even
// surprisingly small arguments.
//
//
//
// Recursive calls versus the value returned
//
// There are actually TWO different problems.
//
// First, the VALUE of the Ackermann function becomes
// too large to represent.
//
// An unsigned long long can represent values only up
// to some fixed maximum.
//
// Thus:
//
//     A(4, 2) = 2^65536 - 3
//
// cannot possibly fit.
//
//
//
// Second, even when the RESULT fits, the direct
// recursive implementation may require an enormous
// amount of computation.
//
// For example:
//
//     A(4, 1) = 65533
//
// fits in an unsigned long long.
//
// That does NOT mean that the direct recursive
// implementation is a sensible way to calculate it.
//
// The recursion itself becomes the problem.
//
//
//
// Stack depth
//
// Every recursive function call normally requires
// information to be stored until that call returns.
//
// This information is stored on the call stack.
//
// For simple recursion such as:
//
//     factorial(n)
//
// the depth is approximately:
//
//     n.
//
// For the Ackermann function, the nested recursion
// can create an enormous call depth.
//
// Consequently, a program attempting sufficiently
// large arguments may fail because it exhausts the
// available call stack long before we have to worry
// about waiting for the final answer.
//
//
//
// What about A(n) = A(n,n)?
//
// Recall our single-argument definition:
//
//     A(n) = A(n,n).
//
// The first few values are:
//
//     A(0) = A(0,0) = 1
//
//     A(1) = A(1,1) = 3
//
//     A(2) = A(2,2) = 7
//
//     A(3) = A(3,3) = 61.
//
// The next value is:
//
//     A(4) = A(4,4).
//
// There is no useful reason to attempt to calculate
// this value using our C++ function.
//
// The jump from:
//
//     A(3) = 61
//
// to:
//
//     A(4)
//
// is enormous.
//
//
//
// Connection with disjoint sets
//
// Curiously, computer scientists also encounter an
// INVERSE of this extremely fast-growing function.
//
// With appropriate implementations of the
// disjoint-set data structure using techniques such
// as:
//
//     union by rank
//
// and:
//
//     path compression,
//
// the amortized cost of operations can be described
// using an inverse Ackermann function.
//
// If the Ackermann function grows extraordinarily
// quickly, its inverse grows extraordinarily slowly.
//
// In practical applications, the inverse Ackermann
// factor is therefore an extremely small number.
//
// We will leave the precise definition and analysis
// of the inverse Ackermann function for a later
// algorithms course.
//
//
//
// One final lesson
//
// Recursion is not merely a different syntax for
// writing a loop.
//
// Recursive definitions can describe extraordinarily
// complicated computations.
//
// Compare:
//
//     factorial:
//
//         n!
//         = n*(n - 1)!
//
//
// with Ackermann:
//
//     A(m,n)
//
//         = A(m - 1, A(m,n - 1)).
//
//
// In factorial, there is one simple recursive chain:
//
//     n
//     |
//     v
//     n - 1
//     |
//     v
//     n - 2
//     |
//     v
//     ...
//
//
// In Ackermann, one recursive calculation can
// determine the argument to ANOTHER recursive
// calculation:
//
//     A(m,n)
//
//        |
//        v
//
//     A(m,n - 1)
//
//        |
//        v
//
//     some possibly enormous value x
//
//        |
//        v
//
//     A(m - 1,x).
//
//
// This nested recursion is what makes the Ackermann
// function such a memorable example.
//
//
//
// Questions:
//
// 1. What are:
//
//        A(0,0), A(0,1), A(0,2), ... ?
//
// 2. Show that:
//
//        A(1,n) = n + 2.
//
// 3. Show that:
//
//        A(2,n) = 2*n + 3.
//
// 4. Verify that:
//
//        A(3,n) = 2^(n + 3) - 3.
//
// 5. Calculate A(4,0).
//
// 6. Calculate A(4,1) using the formula for A(3,n).
//
// 7. Express A(4,2) as a power of two.
//
// 8. Why should you NOT attempt to calculate A(4,2)
//    using this program?
//
// 9. What is unusual about the recursive expression:
//
//        A(m - 1, A(m,n - 1))?
//
// 10. Why can a recursive implementation become
//     impractical even when its final result fits
//     in the return type?
//
// 11. What is the difference between the Ackermann
//     function and the inverse Ackermann function
//     that appears in the analysis of disjoint-set
//     operations?
//
// 12. Why does the inverse of an extraordinarily
//     fast-growing function grow extraordinarily
//     slowly?
//
//
//
// The Ackermann function is not presented here
// because we expect to use this implementation in
// practical programs.
//
// Rather, it demonstrates just how powerful a
// recursive definition can be.
//
// A handful of lines of code:
//
//     if ( m == 0 ) {
//         return n + 1;
//     } else if ( n == 0 ) {
//         return Ackermann( m - 1, 1 );
//     } else {
//         return Ackermann(
//             m - 1,
//             Ackermann( m, n - 1 )
//         );
//     }
//
// describe a function whose values rapidly become
// far larger than anything we could ever explicitly
// calculate or store.