#include <iostream>
#include <unordered_map>
#include <vector>
 
using namespace std;
 
using ull = unsigned long long;
 
struct pair_hash
{
    template <typename T1, typename T2>
    std::size_t operator ()(const std::pair<T1, T2>& pair) const
    {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};
 
using TMem = std::unordered_map<std::pair<int,int>, ull, pair_hash>;
 
// Количество разложений для N блоков равно сумме количеств
// разложений ,где максимальная длина нижнего уровня уровня
// равна N-1,N-2,....
struct task135_recurse
{
    ull operator ()(int N)
    {
        return solve(N, N);
    }
 
private:
    ull solve(int N, int maxN)
    {
        ull result = 0;
 
        if (N < 0) {
            return 0;
        }
 
        if (N == 0) {
            return 1;
        }
 
        for (int i = maxN; i > 0; --i) {
            result += solve(N - i, i - 1);
        }
 
        return result;
    }
};
 
// Оптимизация для предыдущего алгоритма. Запоминаем уже вычисленные
// значения (мемоизация) чтобы не вычислять одно и тоже. По моим
// замерам закэшировать удается до 90% значений
struct task135_recurse_memo
{
    ull operator ()(int N)
    {
        TMem mem;
        return solve(N, N, mem);
    }
 
    std::pair<ull, ull> GetStats()
    {
        return make_pair(Calls, Hits);
    }
 
private:
    ull solve(int N, int maxN, TMem& mem)
    {
        auto it = mem.find(std::make_pair(N,maxN));
 
        ++Calls;
        if (it != mem.end()) {
            ++Hits;
            return it->second;
        }
 
        ull result = 0;
 
        if (N == 0) {
            result = 1;
        }
 
 
        if (N > 0) {
            for (int i = maxN; i > 0; --i) {
                result += solve(N - i, i - 1, mem);
            }
        }
 
        mem[std::make_pair(N,maxN)] = result;
 
        return result;
    }
private:
    ull Calls = 0;
    ull Hits = 0;
};
 
// Здесь мы считаем туже формулу. Но на этот раз
// идем нет от конца к началу , а от начала к концу
// За счет этого избавляемся от рекурсии, но возможно
// проигрываем по памяти и делаем возможно лишнюю работу
// поскольку не знаем какие значения понадобятся потом
struct task135_dynamic_array
{
    ull operator ()(int N)
    {
        return solve(N);
    }
 
private:
    ull get(vector<vector<ull>>& a, int i, int j)
    {
        if (i < 0 || j < 0) {
            return 0;
        }
        return a[i][j];
    }
 
    ull solve(int N)
    {
        vector<vector<ull>> a(N+1, vector<ull>(N+1));
 
        for (int i = 0; i < N; ++i) {
            a[0][i] = 1;
        }
        for (int i = 1; i < N+1; ++i) {
            for (int j = 1; j < N+1; ++j) {
                for (int k = j; k > 0; --k) {
                    a[i][j] += get(a, i - k, k - 1);
                }
            }
        }
        return a[N][N];
    }
};
 
 
// Определим решение немного иначе.
// Количество разложений для N блоков равно сумме количеств
// разложений двух типов
// 1. на нижнем уровне лежит блок длины N
// 2. на нижнем уровне лежит блок длины меньше N
 
struct task135_recurse1
{
    ull operator ()(int N)
    {
        return solve(N, N);
    }
 
private:
    ull solve(int N, int maxN)
    {
        ull result = 0;
 
        if (N < 0 || (maxN == 0 && N != 0)) {
            return 0;
        }
 
        if (N == 0) {
            return 1;
        }
 
        result += solve(N - maxN, maxN - 1) + solve(N, maxN - 1);
 
        return result;
    }
};
 
// Мемоизация предыдущего алгоритма. Опять не вычисляем уже
// вычисленные значения. Для мойих тестов экономилось до 20%
// вычислений (См. GetStats метод).
struct task135_recurse_memo1
{
    ull operator ()(int N)
    {
        TMem mem;
        return solve(N, N, mem);
    }
 
    std::pair<ull, ull> GetStats()
    {
        return make_pair(Calls, Hits);
    }
 
private:
    ull solve(int N, int maxN, TMem& mem)
    {
        auto it = mem.find(std::make_pair(N,maxN));
 
        ++Calls;
        if (it != mem.end()) {
            ++Hits;
            return it->second;
        }
 
        ull result = 0;
 
        if (N == 0 && maxN >= 0) {
            return 1;
        }
 
        if (N > 0 && maxN > 0) {
            result += solve(N - maxN, maxN - 1, mem) + solve(N, maxN - 1, mem);
        }
 
        mem[std::make_pair(N,maxN)] = result;
 
        return result;
    }
private:
    ull Calls = 0;
    ull Hits = 0;
};
 
// Опять нерекурсивная динамика.
// Одем от тачала к концу (от 1 к N)
// За счет этого избавляемся от рекурсии,
// но получаем избыточность по памяти и лишние вычисления
// для ячеек которые возможно не будут нужны
struct task135_dynamic_array1
{
    ull operator ()(int N)
    {
        return solve(N);
    }
 
private:
    ull get(vector<vector<ull>>& a, int i, int j)
    {
        if (i < 0 || j < 0) {
            return 0;
        }
        return a[i][j];
    }
 
    ull solve(int N)
    {
        vector<vector<ull>> a(N+1, vector<ull>(N+1));
 
        for (int i = 0; i < N; ++i) {
            a[0][i] = 1;
        }
        for (int i = 1; i < N+1; ++i) {
            for (int j = 1; j < N+1; ++j) {
                a[i][j] = get(a, i-j,j-1) + get(a, i,j-1);
            }
        }
        return a[N][N];
    }
};
 
 
int main() {
 
    // Прогоняем тесты для всех 6 реализаций задачи
    // вычисляем значение для всех значений от 1 до 100
    // печатаем и убеждаемся что все они совпадают
 
    vector<ull> r1;
    for (int i = 1; i < 101; ++i) {
        r1.push_back(task135_recurse()(i));
    }
 
    vector<ull> r2;
    for (int i = 1; i < 101; ++i) {
        auto a = task135_recurse_memo();
        r2.push_back(a(i));
        //cout << a.GetStats().first << " " << a.GetStats().second << endl;
    }
 
    vector<ull> r3;
    for (int i = 1; i < 101; ++i) {
        r3.push_back(task135_recurse1()(i));
    }
 
    vector<ull> r4;
    for (int i = 1; i < 101; ++i) {
        auto a = task135_recurse_memo1();
        r4.push_back(a(i));
        //cout << a.GetStats().first << " " << a.GetStats().second << endl;
    }
 
    vector<ull> r5;
    for (int i = 1; i < 101; ++i) {
        r5.push_back(task135_dynamic_array()(i));
    }
 
    vector<ull> r6;
    for (int i = 1; i < 101; ++i) {
        r6.push_back(task135_dynamic_array1()(i));
    }
 
    for (int i = 0; i < 100; ++i) {
        cout << (i+1) << "-> " << r1[i] << " " << r2[i] << " " << r3[i] << " " << r4[i] << " " << r5[i] << " " << r6[i] << endl;
    }
 
    return 0;
 
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KI2luY2x1ZGUgPHZlY3Rvcj4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp1c2luZyB1bGwgPSB1bnNpZ25lZCBsb25nIGxvbmc7CgpzdHJ1Y3QgcGFpcl9oYXNoCnsKICAgIHRlbXBsYXRlIDx0eXBlbmFtZSBUMSwgdHlwZW5hbWUgVDI+CiAgICBzdGQ6OnNpemVfdCBvcGVyYXRvciAoKShjb25zdCBzdGQ6OnBhaXI8VDEsIFQyPiYgcGFpcikgY29uc3QKICAgIHsKICAgICAgICByZXR1cm4gc3RkOjpoYXNoPFQxPigpKHBhaXIuZmlyc3QpIF4gc3RkOjpoYXNoPFQyPigpKHBhaXIuc2Vjb25kKTsKICAgIH0KfTsKCnVzaW5nIFRNZW0gPSBzdGQ6OnVub3JkZXJlZF9tYXA8c3RkOjpwYWlyPGludCxpbnQ+LCB1bGwsIHBhaXJfaGFzaD47CgovLyDQmtC+0LvQuNGH0LXRgdGC0LLQviDRgNCw0LfQu9C+0LbQtdC90LjQuSDQtNC70Y8gTiDQsdC70L7QutC+0LIg0YDQsNCy0L3QviDRgdGD0LzQvNC1INC60L7Qu9C40YfQtdGB0YLQsgovLyDRgNCw0LfQu9C+0LbQtdC90LjQuSAs0LPQtNC1INC80LDQutGB0LjQvNCw0LvRjNC90LDRjyDQtNC70LjQvdCwINC90LjQttC90LXQs9C+INGD0YDQvtCy0L3RjyDRg9GA0L7QstC90Y8KLy8g0YDQsNCy0L3QsCBOLTEsTi0yLC4uLi4Kc3RydWN0IHRhc2sxMzVfcmVjdXJzZQp7CiAgICB1bGwgb3BlcmF0b3IgKCkoaW50IE4pCiAgICB7CiAgICAgICAgcmV0dXJuIHNvbHZlKE4sIE4pOwogICAgfQoKcHJpdmF0ZToKICAgIHVsbCBzb2x2ZShpbnQgTiwgaW50IG1heE4pCiAgICB7CiAgICAgICAgdWxsIHJlc3VsdCA9IDA7CgogICAgICAgIGlmIChOIDwgMCkgewogICAgICAgICAgICByZXR1cm4gMDsKICAgICAgICB9CgogICAgICAgIGlmIChOID09IDApIHsKICAgICAgICAgICAgcmV0dXJuIDE7CiAgICAgICAgfQoKICAgICAgICBmb3IgKGludCBpID0gbWF4TjsgaSA+IDA7IC0taSkgewogICAgICAgICAgICByZXN1bHQgKz0gc29sdmUoTiAtIGksIGkgLSAxKTsKICAgICAgICB9CgogICAgICAgIHJldHVybiByZXN1bHQ7CiAgICB9Cn07CgovLyDQntC/0YLQuNC80LjQt9Cw0YbQuNGPINC00LvRjyDQv9GA0LXQtNGL0LTRg9GJ0LXQs9C+INCw0LvQs9C+0YDQuNGC0LzQsC4g0JfQsNC/0L7QvNC40L3QsNC10Lwg0YPQttC1INCy0YvRh9C40YHQu9C10L3QvdGL0LUKLy8g0LfQvdCw0YfQtdC90LjRjyAo0LzQtdC80L7QuNC30LDRhtC40Y8pINGH0YLQvtCx0Ysg0L3QtSDQstGL0YfQuNGB0LvRj9GC0Ywg0L7QtNC90L4g0Lgg0YLQvtC20LUuINCf0L4g0LzQvtC40LwKLy8g0LfQsNC80LXRgNCw0Lwg0LfQsNC60Y3RiNC40YDQvtCy0LDRgtGMINGD0LTQsNC10YLRgdGPINC00L4gOTAlINC30L3QsNGH0LXQvdC40LkKc3RydWN0IHRhc2sxMzVfcmVjdXJzZV9tZW1vCnsKICAgIHVsbCBvcGVyYXRvciAoKShpbnQgTikKICAgIHsKICAgICAgICBUTWVtIG1lbTsKICAgICAgICByZXR1cm4gc29sdmUoTiwgTiwgbWVtKTsKICAgIH0KCiAgICBzdGQ6OnBhaXI8dWxsLCB1bGw+IEdldFN0YXRzKCkKICAgIHsKICAgICAgICByZXR1cm4gbWFrZV9wYWlyKENhbGxzLCBIaXRzKTsKICAgIH0KCnByaXZhdGU6CiAgICB1bGwgc29sdmUoaW50IE4sIGludCBtYXhOLCBUTWVtJiBtZW0pCiAgICB7CiAgICAgICAgYXV0byBpdCA9IG1lbS5maW5kKHN0ZDo6bWFrZV9wYWlyKE4sbWF4TikpOwoKICAgICAgICArK0NhbGxzOwogICAgICAgIGlmIChpdCAhPSBtZW0uZW5kKCkpIHsKICAgICAgICAgICAgKytIaXRzOwogICAgICAgICAgICByZXR1cm4gaXQtPnNlY29uZDsKICAgICAgICB9CgogICAgICAgIHVsbCByZXN1bHQgPSAwOwoKICAgICAgICBpZiAoTiA9PSAwKSB7CiAgICAgICAgICAgIHJlc3VsdCA9IDE7CiAgICAgICAgfQoKCiAgICAgICAgaWYgKE4gPiAwKSB7CiAgICAgICAgICAgIGZvciAoaW50IGkgPSBtYXhOOyBpID4gMDsgLS1pKSB7CiAgICAgICAgICAgICAgICByZXN1bHQgKz0gc29sdmUoTiAtIGksIGkgLSAxLCBtZW0pOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBtZW1bc3RkOjptYWtlX3BhaXIoTixtYXhOKV0gPSByZXN1bHQ7CgogICAgICAgIHJldHVybiByZXN1bHQ7CiAgICB9CnByaXZhdGU6CiAgICB1bGwgQ2FsbHMgPSAwOwogICAgdWxsIEhpdHMgPSAwOwp9OwoKLy8g0JfQtNC10YHRjCDQvNGLINGB0YfQuNGC0LDQtdC8INGC0YPQttC1INGE0L7RgNC80YPQu9GDLiDQndC+INC90LAg0Y3RgtC+0YIg0YDQsNC3Ci8vINC40LTQtdC8INC90LXRgiDQvtGCINC60L7QvdGG0LAg0Log0L3QsNGH0LDQu9GDICwg0LAg0L7RgiDQvdCw0YfQsNC70LAg0Log0LrQvtC90YbRgwovLyDQl9CwINGB0YfQtdGCINGN0YLQvtCz0L4g0LjQt9Cx0LDQstC70Y/QtdC80YHRjyDQvtGCINGA0LXQutGD0YDRgdC40LgsINC90L4g0LLQvtC30LzQvtC20L3QvgovLyDQv9GA0L7QuNCz0YDRi9Cy0LDQtdC8INC/0L4g0L/QsNC80Y/RgtC4INC4INC00LXQu9Cw0LXQvCDQstC+0LfQvNC+0LbQvdC+INC70LjRiNC90Y7RjiDRgNCw0LHQvtGC0YMKLy8g0L/QvtGB0LrQvtC70YzQutGDINC90LUg0LfQvdCw0LXQvCDQutCw0LrQuNC1INC30L3QsNGH0LXQvdC40Y8g0L/QvtC90LDQtNC+0LHRj9GC0YHRjyDQv9C+0YLQvtC8CnN0cnVjdCB0YXNrMTM1X2R5bmFtaWNfYXJyYXkKewogICAgdWxsIG9wZXJhdG9yICgpKGludCBOKQogICAgewogICAgICAgIHJldHVybiBzb2x2ZShOKTsKICAgIH0KCnByaXZhdGU6CiAgICB1bGwgZ2V0KHZlY3Rvcjx2ZWN0b3I8dWxsPj4mIGEsIGludCBpLCBpbnQgaikKICAgIHsKICAgICAgICBpZiAoaSA8IDAgfHwgaiA8IDApIHsKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgfQogICAgICAgIHJldHVybiBhW2ldW2pdOwogICAgfQoKICAgIHVsbCBzb2x2ZShpbnQgTikKICAgIHsKICAgICAgICB2ZWN0b3I8dmVjdG9yPHVsbD4+IGEoTisxLCB2ZWN0b3I8dWxsPihOKzEpKTsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyArK2kpIHsKICAgICAgICAgICAgYVswXVtpXSA9IDE7CiAgICAgICAgfQogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDwgTisxOyArK2kpIHsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDE7IGogPCBOKzE7ICsraikgewogICAgICAgICAgICAgICAgZm9yIChpbnQgayA9IGo7IGsgPiAwOyAtLWspIHsKICAgICAgICAgICAgICAgICAgICBhW2ldW2pdICs9IGdldChhLCBpIC0gaywgayAtIDEpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBhW05dW05dOwogICAgfQp9OwoKCi8vINCe0L/RgNC10LTQtdC70LjQvCDRgNC10YjQtdC90LjQtSDQvdC10LzQvdC+0LPQviDQuNC90LDRh9C1LgovLyDQmtC+0LvQuNGH0LXRgdGC0LLQviDRgNCw0LfQu9C+0LbQtdC90LjQuSDQtNC70Y8gTiDQsdC70L7QutC+0LIg0YDQsNCy0L3QviDRgdGD0LzQvNC1INC60L7Qu9C40YfQtdGB0YLQsgovLyDRgNCw0LfQu9C+0LbQtdC90LjQuSDQtNCy0YPRhSDRgtC40L/QvtCyCi8vIDEuINC90LAg0L3QuNC20L3QtdC8INGD0YDQvtCy0L3QtSDQu9C10LbQuNGCINCx0LvQvtC6INC00LvQuNC90YsgTgovLyAyLiDQvdCwINC90LjQttC90LXQvCDRg9GA0L7QstC90LUg0LvQtdC20LjRgiDQsdC70L7QuiDQtNC70LjQvdGLINC80LXQvdGM0YjQtSBOCgpzdHJ1Y3QgdGFzazEzNV9yZWN1cnNlMQp7CiAgICB1bGwgb3BlcmF0b3IgKCkoaW50IE4pCiAgICB7CiAgICAgICAgcmV0dXJuIHNvbHZlKE4sIE4pOwogICAgfQoKcHJpdmF0ZToKICAgIHVsbCBzb2x2ZShpbnQgTiwgaW50IG1heE4pCiAgICB7CiAgICAgICAgdWxsIHJlc3VsdCA9IDA7CgogICAgICAgIGlmIChOIDwgMCB8fCAobWF4TiA9PSAwICYmIE4gIT0gMCkpIHsKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgfQoKICAgICAgICBpZiAoTiA9PSAwKSB7CiAgICAgICAgICAgIHJldHVybiAxOwogICAgICAgIH0KCiAgICAgICAgcmVzdWx0ICs9IHNvbHZlKE4gLSBtYXhOLCBtYXhOIC0gMSkgKyBzb2x2ZShOLCBtYXhOIC0gMSk7CgogICAgICAgIHJldHVybiByZXN1bHQ7CiAgICB9Cn07CgovLyDQnNC10LzQvtC40LfQsNGG0LjRjyDQv9GA0LXQtNGL0LTRg9GJ0LXQs9C+INCw0LvQs9C+0YDQuNGC0LzQsC4g0J7Qv9GP0YLRjCDQvdC1INCy0YvRh9C40YHQu9GP0LXQvCDRg9C20LUKLy8g0LLRi9GH0LjRgdC70LXQvdC90YvQtSDQt9C90LDRh9C10L3QuNGPLiDQlNC70Y8g0LzQvtC50LjRhSDRgtC10YHRgtC+0LIg0Y3QutC+0L3QvtC80LjQu9C+0YHRjCDQtNC+IDIwJQovLyDQstGL0YfQuNGB0LvQtdC90LjQuSAo0KHQvC4gR2V0U3RhdHMg0LzQtdGC0L7QtCkuCnN0cnVjdCB0YXNrMTM1X3JlY3Vyc2VfbWVtbzEKewogICAgdWxsIG9wZXJhdG9yICgpKGludCBOKQogICAgewogICAgICAgIFRNZW0gbWVtOwogICAgICAgIHJldHVybiBzb2x2ZShOLCBOLCBtZW0pOwogICAgfQoKICAgIHN0ZDo6cGFpcjx1bGwsIHVsbD4gR2V0U3RhdHMoKQogICAgewogICAgICAgIHJldHVybiBtYWtlX3BhaXIoQ2FsbHMsIEhpdHMpOwogICAgfQoKcHJpdmF0ZToKICAgIHVsbCBzb2x2ZShpbnQgTiwgaW50IG1heE4sIFRNZW0mIG1lbSkKICAgIHsKICAgICAgICBhdXRvIGl0ID0gbWVtLmZpbmQoc3RkOjptYWtlX3BhaXIoTixtYXhOKSk7CgogICAgICAgICsrQ2FsbHM7CiAgICAgICAgaWYgKGl0ICE9IG1lbS5lbmQoKSkgewogICAgICAgICAgICArK0hpdHM7CiAgICAgICAgICAgIHJldHVybiBpdC0+c2Vjb25kOwogICAgICAgIH0KCiAgICAgICAgdWxsIHJlc3VsdCA9IDA7CgogICAgICAgIGlmIChOID09IDAgJiYgbWF4TiA+PSAwKSB7CiAgICAgICAgICAgIHJldHVybiAxOwogICAgICAgIH0KCiAgICAgICAgaWYgKE4gPiAwICYmIG1heE4gPiAwKSB7CiAgICAgICAgICAgIHJlc3VsdCArPSBzb2x2ZShOIC0gbWF4TiwgbWF4TiAtIDEsIG1lbSkgKyBzb2x2ZShOLCBtYXhOIC0gMSwgbWVtKTsKICAgICAgICB9CgogICAgICAgIG1lbVtzdGQ6Om1ha2VfcGFpcihOLG1heE4pXSA9IHJlc3VsdDsKCiAgICAgICAgcmV0dXJuIHJlc3VsdDsKICAgIH0KcHJpdmF0ZToKICAgIHVsbCBDYWxscyA9IDA7CiAgICB1bGwgSGl0cyA9IDA7Cn07CgovLyDQntC/0Y/RgtGMINC90LXRgNC10LrRg9GA0YHQuNCy0L3QsNGPINC00LjQvdCw0LzQuNC60LAuCi8vINCe0LTQtdC8INC+0YIg0YLQsNGH0LDQu9CwINC6INC60L7QvdGG0YMgKNC+0YIgMSDQuiBOKQovLyDQl9CwINGB0YfQtdGCINGN0YLQvtCz0L4g0LjQt9Cx0LDQstC70Y/QtdC80YHRjyDQvtGCINGA0LXQutGD0YDRgdC40LgsCi8vINC90L4g0L/QvtC70YPRh9Cw0LXQvCDQuNC30LHRi9GC0L7Rh9C90L7RgdGC0Ywg0L/QviDQv9Cw0LzRj9GC0Lgg0Lgg0LvQuNGI0L3QuNC1INCy0YvRh9C40YHQu9C10L3QuNGPCi8vINC00LvRjyDRj9GH0LXQtdC6INC60L7RgtC+0YDRi9C1INCy0L7Qt9C80L7QttC90L4g0L3QtSDQsdGD0LTRg9GCINC90YPQttC90YsKc3RydWN0IHRhc2sxMzVfZHluYW1pY19hcnJheTEKewogICAgdWxsIG9wZXJhdG9yICgpKGludCBOKQogICAgewogICAgICAgIHJldHVybiBzb2x2ZShOKTsKICAgIH0KCnByaXZhdGU6CiAgICB1bGwgZ2V0KHZlY3Rvcjx2ZWN0b3I8dWxsPj4mIGEsIGludCBpLCBpbnQgaikKICAgIHsKICAgICAgICBpZiAoaSA8IDAgfHwgaiA8IDApIHsKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgfQogICAgICAgIHJldHVybiBhW2ldW2pdOwogICAgfQoKICAgIHVsbCBzb2x2ZShpbnQgTikKICAgIHsKICAgICAgICB2ZWN0b3I8dmVjdG9yPHVsbD4+IGEoTisxLCB2ZWN0b3I8dWxsPihOKzEpKTsKCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyArK2kpIHsKICAgICAgICAgICAgYVswXVtpXSA9IDE7CiAgICAgICAgfQogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDwgTisxOyArK2kpIHsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDE7IGogPCBOKzE7ICsraikgewogICAgICAgICAgICAgICAgYVtpXVtqXSA9IGdldChhLCBpLWosai0xKSArIGdldChhLCBpLGotMSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuIGFbTl1bTl07CiAgICB9Cn07CgoKaW50IG1haW4oKSB7CgogICAgLy8g0J/RgNC+0LPQvtC90Y/QtdC8INGC0LXRgdGC0Ysg0LTQu9GPINCy0YHQtdGFIDYg0YDQtdCw0LvQuNC30LDRhtC40Lkg0LfQsNC00LDRh9C4CiAgICAvLyDQstGL0YfQuNGB0LvRj9C10Lwg0LfQvdCw0YfQtdC90LjQtSDQtNC70Y8g0LLRgdC10YUg0LfQvdCw0YfQtdC90LjQuSDQvtGCIDEg0LTQviAxMDAKICAgIC8vINC/0LXRh9Cw0YLQsNC10Lwg0Lgg0YPQsdC10LbQtNCw0LXQvNGB0Y8g0YfRgtC+INCy0YHQtSDQvtC90Lgg0YHQvtCy0L/QsNC00LDRjtGCCgogICAgdmVjdG9yPHVsbD4gcjE7CiAgICBmb3IgKGludCBpID0gMTsgaSA8IDEwMTsgKytpKSB7CiAgICAgICAgcjEucHVzaF9iYWNrKHRhc2sxMzVfcmVjdXJzZSgpKGkpKTsKICAgIH0KCiAgICB2ZWN0b3I8dWxsPiByMjsKICAgIGZvciAoaW50IGkgPSAxOyBpIDwgMTAxOyArK2kpIHsKICAgICAgICBhdXRvIGEgPSB0YXNrMTM1X3JlY3Vyc2VfbWVtbygpOwogICAgICAgIHIyLnB1c2hfYmFjayhhKGkpKTsKICAgICAgICAvL2NvdXQgPDwgYS5HZXRTdGF0cygpLmZpcnN0IDw8ICIgIiA8PCBhLkdldFN0YXRzKCkuc2Vjb25kIDw8IGVuZGw7CiAgICB9CgogICAgdmVjdG9yPHVsbD4gcjM7CiAgICBmb3IgKGludCBpID0gMTsgaSA8IDEwMTsgKytpKSB7CiAgICAgICAgcjMucHVzaF9iYWNrKHRhc2sxMzVfcmVjdXJzZTEoKShpKSk7CiAgICB9CgogICAgdmVjdG9yPHVsbD4gcjQ7CiAgICBmb3IgKGludCBpID0gMTsgaSA8IDEwMTsgKytpKSB7CiAgICAgICAgYXV0byBhID0gdGFzazEzNV9yZWN1cnNlX21lbW8xKCk7CiAgICAgICAgcjQucHVzaF9iYWNrKGEoaSkpOwogICAgICAgIC8vY291dCA8PCBhLkdldFN0YXRzKCkuZmlyc3QgPDwgIiAiIDw8IGEuR2V0U3RhdHMoKS5zZWNvbmQgPDwgZW5kbDsKICAgIH0KCiAgICB2ZWN0b3I8dWxsPiByNTsKICAgIGZvciAoaW50IGkgPSAxOyBpIDwgMTAxOyArK2kpIHsKICAgICAgICByNS5wdXNoX2JhY2sodGFzazEzNV9keW5hbWljX2FycmF5KCkoaSkpOwogICAgfQoKICAgIHZlY3Rvcjx1bGw+IHI2OwogICAgZm9yIChpbnQgaSA9IDE7IGkgPCAxMDE7ICsraSkgewogICAgICAgIHI2LnB1c2hfYmFjayh0YXNrMTM1X2R5bmFtaWNfYXJyYXkxKCkoaSkpOwogICAgfQoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMTAwOyArK2kpIHsKICAgICAgICBjb3V0IDw8IChpKzEpIDw8ICItPiAiIDw8IHIxW2ldIDw8ICIgIiA8PCByMltpXSA8PCAiICIgPDwgcjNbaV0gPDwgIiAiIDw8IHI0W2ldIDw8ICIgIiA8PCByNVtpXSA8PCAiICIgPDwgcjZbaV0gPDwgZW5kbDsKICAgIH0KCiAgICByZXR1cm4gMDsKCn0=