Ideone.com

download

copy

#include <iostream>
#include <vector>
#include <sstream>
#include <iomanip>
 
#include <limits.h>
#include <stdlib.h>
 
 
typedef int ELEM_TYPE;
typedef long long PRODUCT_TYPE;
static const ELEM_TYPE BASE = 1000000000;
static const ELEM_TYPE UPPER_BOUND = 999999999;
static const ELEM_TYPE DIGIT_COUNT = 9;
static const int powersOfTen[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 };
class InfInt
{
    friend std::ostream& operator<<(std::ostream &s, const InfInt &n);
    friend std::istream& operator>>(std::istream &s, InfInt &val);
 
public:
    /* some constants */
    static const InfInt zero;
    static const InfInt one;
    static const InfInt two;
 
    /* constructors */
    InfInt();
    InfInt(const char* c);
    InfInt(const std::string& s);
    InfInt(int l);
    InfInt(long l);
    InfInt(long long l);
    InfInt(unsigned int l);
    InfInt(unsigned long l);
    InfInt(unsigned long long l);
 
    /* assignment operators */
    const InfInt& operator=(const char* c);
    const InfInt& operator=(const std::string& s);
    const InfInt& operator=(int l);
    const InfInt& operator=(long l);
    const InfInt& operator=(long long l);
    const InfInt& operator=(unsigned int l);
    const InfInt& operator=(unsigned long l);
    const InfInt& operator=(unsigned long long l);
 
    /* unary increment/decrement operators */
    const InfInt& operator++();
    const InfInt& operator--();
    InfInt operator++(int);
    InfInt operator--(int);
 
    /* operational assignments */
    const InfInt& operator+=(const InfInt& rhs);
    const InfInt& operator-=(const InfInt& rhs);
    const InfInt& operator*=(const InfInt& rhs);
    const InfInt& operator/=(const InfInt& rhs); // throw
    const InfInt& operator%=(const InfInt& rhs); // throw
    const InfInt& operator*=(ELEM_TYPE rhs);
 
    /* operations */
    InfInt operator-() const;
    InfInt operator+(const InfInt& rhs) const;
    InfInt operator-(const InfInt& rhs) const;
    InfInt operator*(const InfInt& rhs) const;
    InfInt operator/(const InfInt& rhs) const; // throw
    InfInt operator%(const InfInt& rhs) const; // throw
    InfInt operator*(ELEM_TYPE rhs) const;
 
    /* relational operations */
    bool operator==(const InfInt& rhs) const;
    bool operator!=(const InfInt& rhs) const;
    bool operator<(const InfInt& rhs) const;
    bool operator<=(const InfInt& rhs) const;
    bool operator>(const InfInt& rhs) const;
    bool operator>=(const InfInt& rhs) const;
 
    /* integer square root */
    InfInt intSqrt() const; // throw
 
    /* digit operations */
    char digitAt(size_t i) const; // throw
    size_t numberOfDigits() const;
 
    /* size in bytes */
    size_t size() const;
 
    /* string conversion */
    std::string toString() const;
 
    /* conversion to primitive types */
    int toInt() const; // throw
    long toLong() const; // throw
    long long toLongLong() const; // throw
    unsigned int toUnsignedInt() const; // throw
    unsigned long toUnsignedLong() const; // throw
    unsigned long long toUnsignedLongLong() const; // throw
 
private:
    static ELEM_TYPE dInR(const InfInt& R, const InfInt& D);
    static void multiplyByDigit(ELEM_TYPE factor, std::vector<ELEM_TYPE>& val);
 
    void correct(bool justCheckLeadingZeros = false, bool hasValidSign = false);
    void fromString(const std::string& s);
    void optimizeSqrtSearchBounds(InfInt& lo, InfInt& hi) const;
    void truncateToBase();
    bool equalizeSigns();
    void removeLeadingZeros();
 
    std::vector<ELEM_TYPE> val; // number with base FACTOR
    bool pos; // true if number is positive
};
 
const InfInt InfInt::zero = 0;
const InfInt InfInt::one = 1;
const InfInt InfInt::two = 2;
 
inline InfInt::InfInt() : pos(true)
{
    val.push_back((ELEM_TYPE) 0);
}
 
inline InfInt::InfInt(const char* c)
{
    fromString(c);
}
 
inline InfInt::InfInt(const std::string& s)
{
    fromString(s);
}
 
inline InfInt::InfInt(int l) : pos(l >= 0)
{
    if (!pos)
    {
        l = -l;
    }
    do
    {
        div_t dt = div(l, BASE);
        val.push_back((ELEM_TYPE) dt.rem);
        l = dt.quot;
    } while (l > 0);
}
 
inline InfInt::InfInt(long l) : pos(l >= 0)
{
    if (!pos)
    {
        l = -l;
    }
    do
    {
        ldiv_t dt = ldiv(l, BASE);
        val.push_back((ELEM_TYPE) dt.rem);
        l = dt.quot;
    } while (l > 0);
}
 
inline InfInt::InfInt(long long l) : pos(l >= 0)
{
    if (!pos)
    {
        l = -l;
    }
    do
    {
        val.push_back((ELEM_TYPE) (l % BASE));
        l = l / BASE;
    } while (l > 0);
}
 
inline InfInt::InfInt(unsigned int l) : pos(true)
{
    do
    {
        val.push_back((ELEM_TYPE) (l % BASE));
        l = l / BASE;
    } while (l > 0);
}
 
inline InfInt::InfInt(unsigned long l) : pos(true)
{
    do
    {
        val.push_back((ELEM_TYPE) (l % BASE));
        l = l / BASE;
    } while (l > 0);
}
 
inline InfInt::InfInt(unsigned long long l) : pos(true)
{
    do
    {
        val.push_back((ELEM_TYPE) (l % BASE));
        l = l / BASE;
    } while (l > 0);
}
 
inline const InfInt& InfInt::operator=(const char* c)
{
    fromString(c);
    return *this;
}
 
inline const InfInt& InfInt::operator=(const std::string& s)
{
    fromString(s);
    return *this;
}
 
inline const InfInt& InfInt::operator=(int l)
{
    pos = l >= 0;
    val.clear();
    if (!pos)
    {
        l = -l;
    }
    do
    {
        div_t dt = div(l, BASE);
        val.push_back((ELEM_TYPE) dt.rem);
        l = dt.quot;
    } while (l > 0);
    return *this;
}
 
inline const InfInt& InfInt::operator=(long l)
{
    pos = l >= 0;
    val.clear();
    if (!pos)
    {
        l = -l;
    }
    do
    {
        ldiv_t dt = ldiv(l, BASE);
        val.push_back((ELEM_TYPE) dt.rem);
        l = dt.quot;
    } while (l > 0);
    return *this;
}
 
inline const InfInt& InfInt::operator=(long long l)
{
    pos = l >= 0;
    val.clear();
    if (!pos)
    {
        l = -l;
    }
    do
    {
        val.push_back((ELEM_TYPE) (l % BASE));
        l = l / BASE;
    } while (l > 0);
    return *this;
}
 
inline const InfInt& InfInt::operator=(unsigned int l)
{
    pos = true;
    val.clear();
    do
    {
        val.push_back((ELEM_TYPE) (l % BASE));
        l = l / BASE;
    } while (l > 0);
    return *this;
}
 
inline const InfInt& InfInt::operator=(unsigned long l)
{
    pos = true;
    val.clear();
    do
    {
        val.push_back((ELEM_TYPE) (l % BASE));
        l = l / BASE;
    } while (l > 0);
    return *this;
}
 
inline const InfInt& InfInt::operator=(unsigned long long l)
{
    pos = true;
    val.clear();
    do
    {
        val.push_back((ELEM_TYPE) (l % BASE));
        l = l / BASE;
    } while (l > 0);
    return *this;
}
 
inline const InfInt& InfInt::operator++()
{
    val[0] += (pos ? 1 : -1);
    this->correct(false, true);
    return *this;
}
 
inline const InfInt& InfInt::operator--()
{
    val[0] -= (pos ? 1 : -1);
    this->correct(false, true);
    return *this;
}
 
inline InfInt InfInt::operator++(int)
{
    InfInt result = *this;
    val[0] += (pos ? 1 : -1);
    this->correct(false, true);
    return result;
}
 
inline InfInt InfInt::operator--(int)
{
    InfInt result = *this;
    val[0] -= (pos ? 1 : -1);
    this->correct(false, true);
    return result;
}
 
inline const InfInt& InfInt::operator+=(const InfInt& rhs)
{
    if (rhs.val.size() > val.size())
    {
        val.resize(rhs.val.size(), 0);
    }
    for (size_t i = 0; i < val.size(); ++i)
    {
        val[i] = (pos ? val[i] : -val[i]) + (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0);
    }
    correct();
    return *this;
}
 
inline const InfInt& InfInt::operator-=(const InfInt& rhs)
{
    if (rhs.val.size() > val.size())
    {
        val.resize(rhs.val.size(), 0);
    }
    for (size_t i = 0; i < val.size(); ++i)
    {
        val[i] = (pos ? val[i] : -val[i]) - (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0);
    }
    correct();
    return *this;
}
 
inline const InfInt& InfInt::operator*=(const InfInt& rhs)
{
    // TODO: optimize (do not use operator*)
    *this = *this * rhs;
    return *this;
}
 
inline const InfInt& InfInt::operator/=(const InfInt& rhs)
{
    if (rhs == zero)
    {
        std::cerr << "Division by zero!" << std::endl;
        return *this;
    }
    InfInt R, D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this);
    bool oldpos = pos;
    val.clear();
    val.resize(N.val.size(), 0);
    for (int i = (int) N.val.size() - 1; i >= 0; --i)
    {
        R.val.insert(R.val.begin(), (ELEM_TYPE) 0);
        R.val[0] = N.val[i];
        R.correct(true);
        ELEM_TYPE cnt = dInR(R, D);
        R -= D * cnt;
        val[i] += cnt;
    }
    correct();
    pos = (val.size() == 1 && val[0] == 0) ? true : (oldpos == rhs.pos);
    return *this;
}
 
inline const InfInt& InfInt::operator%=(const InfInt& rhs)
{
    if (rhs == zero)
    {
        std::cerr << "Division by zero!" << std::endl;
        return zero;
    }
    InfInt D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this);
    bool oldpos = pos;
    val.clear();
    for (int i = (int) N.val.size() - 1; i >= 0; --i)
    {
        val.insert(val.begin(), (ELEM_TYPE) 0);
        val[0] = N.val[i];
        correct(true);
        *this -= D * dInR(*this, D);
    }
    correct();
    pos = (val.size() == 1 && val[0] == 0) ? true : oldpos;
    return *this;
}
 
inline const InfInt& InfInt::operator*=(ELEM_TYPE rhs)
{
    ELEM_TYPE factor = rhs < 0 ? -rhs : rhs;
    bool oldpos = pos;
    multiplyByDigit(factor, val);
    correct();
    pos = (val.size() == 1 && val[0] == 0) ? true : (oldpos == (rhs >= 0));
    return *this;
}
 
inline InfInt InfInt::operator-() const
{//PROFILED_SCOPE
    InfInt result = *this;
    result.pos = !pos;
    return result;
}
 
inline InfInt InfInt::operator+(const InfInt& rhs) const
{//PROFILED_SCOPE
    InfInt result;
    result.val.resize(val.size() > rhs.val.size() ? val.size() : rhs.val.size(), 0);
    for (size_t i = 0; i < val.size() || i < rhs.val.size(); ++i)
    {
        result.val[i] = (i < val.size() ? (pos ? val[i] : -val[i]) : 0) + (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0);
    }
    result.correct();
    return result;
}
 
inline InfInt InfInt::operator-(const InfInt& rhs) const
{//PROFILED_SCOPE
    InfInt result;
    result.val.resize(val.size() > rhs.val.size() ? val.size() : rhs.val.size(), 0);
    for (size_t i = 0; i < val.size() || i < rhs.val.size(); ++i)
    {
        result.val[i] = (i < val.size() ? (pos ? val[i] : -val[i]) : 0) - (i < rhs.val.size() ? (rhs.pos ? rhs.val[i] : -rhs.val[i]) : 0);
    }
    result.correct();
    return result;
}
 
inline InfInt InfInt::operator*(const InfInt& rhs) const
{//PROFILED_SCOPE
    InfInt result;
    result.val.resize(val.size() + rhs.val.size(), 0);
    PRODUCT_TYPE carry = 0;
    size_t digit = 0;
    for (;; ++digit)
    {//PROFILED_SCOPE
        //result.val[digit] = (ELEM_TYPE) (carry % BASE);
        //carry /= BASE;
 
        PRODUCT_TYPE oldcarry = carry;
        carry /= BASE;
        result.val[digit] = (ELEM_TYPE) (oldcarry - carry * BASE);
 
        bool found = false;
        for (size_t i = digit < rhs.val.size() ? 0 : digit - rhs.val.size() + 1; i < val.size() && i <= digit; ++i)
        {//PROFILED_SCOPE
            PRODUCT_TYPE pval = result.val[digit] + val[i] * (PRODUCT_TYPE) rhs.val[digit - i];
            if (pval >= BASE || pval <= -BASE)
            {//PROFILED_SCOPE
                //carry += pval / BASE;
                //pval %= BASE;
 
                PRODUCT_TYPE quot = pval / BASE;
                carry += quot;
                pval -= quot * BASE;
            }
            result.val[digit] = (ELEM_TYPE) pval;
            found = true;
        }
        if (!found)
        {//PROFILED_SCOPE
            break;
        }
    }
    for (; carry > 0; ++digit)
    {//PROFILED_SCOPE
        result.val[digit] = (ELEM_TYPE) (carry % BASE);
        carry /= BASE;
    }
    result.correct();
    result.pos = (result.val.size() == 1 && result.val[0] == 0) ? true : (pos == rhs.pos);
    return result;
}
 
inline InfInt InfInt::operator/(const InfInt& rhs) const
{//PROFILED_SCOPE
    if (rhs == zero)
    {
        std::cerr << "Division by zero!" << std::endl;
        return zero;
    }
    InfInt Q, R, D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this);
    Q.val.resize(N.val.size(), 0);
    for (int i = (int) N.val.size() - 1; i >= 0; --i)
    {//PROFILED_SCOPE
        R.val.insert(R.val.begin(), (ELEM_TYPE) 0);
        R.val[0] = N.val[i];
        R.correct(true);
        ELEM_TYPE cnt = dInR(R, D);
        R -= D * cnt;
        Q.val[i] += cnt;
    }
    Q.correct();
    Q.pos = (Q.val.size() == 1 && Q.val[0] == 0) ? true : (pos == rhs.pos);
    return Q;
}
 
inline InfInt InfInt::operator%(const InfInt& rhs) const
{//PROFILED_SCOPE
    if (rhs == zero)
    {
        std::cerr << "Division by zero!" << std::endl;
        return zero;
    }
    InfInt R, D = (rhs.pos ? rhs : -rhs), N = (pos ? *this : -*this);
    for (int i = (int) N.val.size() - 1; i >= 0; --i)
    {
        R.val.insert(R.val.begin(), (ELEM_TYPE) 0);
        R.val[0] = N.val[i];
        R.correct(true);
        R -= D * dInR(R, D);
    }
    R.correct();
    R.pos = (R.val.size() == 1 && R.val[0] == 0) ? true : pos;
    return R;
}
 
inline InfInt InfInt::operator*(ELEM_TYPE rhs) const
{//PROFILED_SCOPE
    InfInt result = *this;
    ELEM_TYPE factor = rhs < 0 ? -rhs : rhs;
    multiplyByDigit(factor, result.val);
    result.correct();
    result.pos = (result.val.size() == 1 && result.val[0] == 0) ? true : (pos == (rhs >= 0));
    return result;
}
 
inline bool InfInt::operator==(const InfInt& rhs) const
{//PROFILED_SCOPE
    if (pos != rhs.pos || val.size() != rhs.val.size())
    {
        return false;
    }
    for (int i = (int) val.size() - 1; i >= 0; --i)
    {
        if (val[i] != rhs.val[i])
        {
            return false;
        }
    }
    return true;
}
 
inline bool InfInt::operator!=(const InfInt& rhs) const
{//PROFILED_SCOPE
    if (pos != rhs.pos || val.size() != rhs.val.size())
    {
        return true;
    }
    for (int i = (int) val.size() - 1; i >= 0; --i)
    {
        if (val[i] != rhs.val[i])
        {
            return true;
        }
    }
    return false;
}
 
inline bool InfInt::operator<(const InfInt& rhs) const
{//PROFILED_SCOPE
    if (pos && !rhs.pos)
    {
        return false;
    }
    if (!pos && rhs.pos)
    {
        return true;
    }
    if (val.size() > rhs.val.size())
    {
        return pos ? false : true;
    }
    if (val.size() < rhs.val.size())
    {
        return pos ? true : false;
    }
    for (int i = (int) val.size() - 1; i >= 0; --i)
    {
        if (val[i] < rhs.val[i])
        {
            return pos ? true : false;
        }
        if (val[i] > rhs.val[i])
        {
            return pos ? false : true;
        }
    }
    return false;
}
 
inline bool InfInt::operator<=(const InfInt& rhs) const
{//PROFILED_SCOPE
    if (pos && !rhs.pos)
    {
        return false;
    }
    if (!pos && rhs.pos)
    {
        return true;
    }
    if (val.size() > rhs.val.size())
    {
        return pos ? false : true;
    }
    if (val.size() < rhs.val.size())
    {
        return pos ? true : false;
    }
    for (int i = (int) val.size() - 1; i >= 0; --i)
    {
        if (val[i] < rhs.val[i])
        {
            return pos ? true : false;
        }
        if (val[i] > rhs.val[i])
        {
            return pos ? false : true;
        }
    }
    return true;
}
 
inline bool InfInt::operator>(const InfInt& rhs) const
{//PROFILED_SCOPE
    if (pos && !rhs.pos)
    {
        return true;
    }
    if (!pos && rhs.pos)
    {
        return false;
    }
    if (val.size() > rhs.val.size())
    {
        return pos ? true : false;
    }
    if (val.size() < rhs.val.size())
    {
        return pos ? false : true;
    }
    for (int i = (int) val.size() - 1; i >= 0; --i)
    {
        if (val[i] < rhs.val[i])
        {
            return pos ? false : true;
        }
        if (val[i] > rhs.val[i])
        {
            return pos ? true : false;
        }
    }
    return false;
}
 
inline bool InfInt::operator>=(const InfInt& rhs) const
{//PROFILED_SCOPE
    if (pos && !rhs.pos)
    {
        return true;
    }
    if (!pos && rhs.pos)
    {
        return false;
    }
    if (val.size() > rhs.val.size())
    {
        return pos ? true : false;
    }
    if (val.size() < rhs.val.size())
    {
        return pos ? false : true;
    }
    for (int i = (int) val.size() - 1; i >= 0; --i)
    {
        if (val[i] < rhs.val[i])
        {
            return pos ? false : true;
        }
        if (val[i] > rhs.val[i])
        {
            return pos ? true : false;
        }
    }
    return true;
}
 
inline void InfInt::optimizeSqrtSearchBounds(InfInt& lo, InfInt& hi) const
{//PROFILED_SCOPE
    InfInt hdn = one;
    for (int i = (int) this->numberOfDigits() / 2; i >= 2; --i)
    {
        hdn *= 10;
    }
    if (lo < hdn)
    {
        lo = hdn;
    }
    hdn *= 100;
    if (hi > hdn)
    {
        hi = hdn;
    }
}
 
inline InfInt InfInt::intSqrt() const
{//PROFILED_SCOPE
    if (*this <= zero)
    {
        std::cerr << "intSqrt called for non-positive integer: " << *this << std::endl;
        return zero;
    }
    InfInt hi = *this / two + one, lo = zero, mid, mid2;
    optimizeSqrtSearchBounds(lo, hi);
    do
    {
        mid = (hi + lo) / two; // 8 factor
        mid2 = mid * mid; // 1 factor
        if (mid2 == *this)
        {
            lo = mid;
            break;
        }
        else if (mid2 < *this)
        {
            lo = mid;
        }
        else
        {
            hi = mid;
        }
    } while (lo < hi - one && mid2 != *this);
    return lo;
}
 
inline char InfInt::digitAt(size_t i) const
{//PROFILED_SCOPE
    if (numberOfDigits() <= i)
    {
        std::cerr << "Invalid digit index: " << i << std::endl;
        return -1;
    }
    return (val[i / DIGIT_COUNT] / powersOfTen[i % DIGIT_COUNT]) % 10;
}
 
inline size_t InfInt::numberOfDigits() const
{//PROFILED_SCOPE
    return (val.size() - 1) * DIGIT_COUNT
    + (val.back() > 99999999 ? 9 : (val.back() > 9999999 ? 8 : (val.back() > 999999 ? 7 : (val.back() > 99999 ? 6 :
                                                                                           (val.back() > 9999 ? 5 : (val.back() > 999 ? 4 : (val.back() > 99 ? 3 : (val.back() > 9 ? 2 : 1))))))));
}
 
inline std::string InfInt::toString() const
{//PROFILED_SCOPE
    std::ostringstream oss;
    oss << *this;
    return oss.str();
}
 
inline size_t InfInt::size() const
{//PROFILED_SCOPE
    return val.size() * sizeof(ELEM_TYPE) + sizeof(bool);
}
 
inline int InfInt::toInt() const
{//PROFILED_SCOPE
    if (*this > INT_MAX || *this < INT_MIN)
    std::cerr << "Out of INT bounds: " << *this << std::endl;
    int result = 0;
    for (int i = (int) val.size() - 1; i >= 0; --i)
    {
        result = result * BASE + val[i];
    }
    return pos ? result : -result;
}
 
inline long InfInt::toLong() const
{//PROFILED_SCOPE
    if (*this > LONG_MAX || *this < LONG_MIN)
    std::cerr << "Out of LONG bounds: " << *this << std::endl;
    long result = 0;
    for (int i = (int) val.size() - 1; i >= 0; --i)
    {
        result = result * BASE + val[i];
    }
    return pos ? result : -result;
}
 
inline long long InfInt::toLongLong() const
{//PROFILED_SCOPE
    if (*this > LONG_LONG_MAX || *this < LONG_LONG_MIN)
    std::cerr << "Out of LLONG bounds: " << *this << std::endl;
    long long result = 0;
    for (int i = (int) val.size() - 1; i >= 0; --i)
    {
        result = result * BASE + val[i];
    }
    return pos ? result : -result;
}
 
inline unsigned int InfInt::toUnsignedInt() const
{//PROFILED_SCOPE
    if (!pos || *this > UINT_MAX)
    std::cerr << "Out of UINT bounds: " << *this << std::endl;
    unsigned int result = 0;
    for (int i = (int) val.size() - 1; i >= 0; --i)
    {
        result = result * BASE + val[i];
    }
    return result;
}
 
inline unsigned long InfInt::toUnsignedLong() const
{//PROFILED_SCOPE
    if (!pos || *this > ULONG_MAX)
    std::cerr << "Out of ULONG bounds: " << *this << std::endl;
    unsigned long result = 0;
    for (int i = (int) val.size() - 1; i >= 0; --i)
    {
        result = result * BASE + val[i];
    }
    return result;
}
 
inline unsigned long long InfInt::toUnsignedLongLong() const
{//PROFILED_SCOPE
    if (!pos || *this > ULONG_LONG_MAX)
    std::cerr << "Out of ULLONG bounds: " << *this << std::endl;
    unsigned long long result = 0;
    for (int i = (int) val.size() - 1; i >= 0; --i)
    {
        result = result * BASE + val[i];
    }
    return result;
}
 
inline void InfInt::truncateToBase()
{//PROFILED_SCOPE
    for (size_t i = 0; i < val.size(); ++i) // truncate each
    {
        if (val[i] >= BASE || val[i] <= -BASE)
        {//PROFILED_SCOPE
            div_t dt = div(val[i], BASE);
            val[i] = dt.rem;
            if (i + 1 >= val.size())
            {//PROFILED_SCOPE
                val.push_back(dt.quot);
            }
            else
            {//PROFILED_SCOPE
                val[i + 1] += dt.quot;
            }
        }
    }
}
 
inline bool InfInt::equalizeSigns()
{//PROFILED_SCOPE
    bool isPositive = true;
    int i = (int) ((val.size())) - 1;
    for (; i >= 0; --i)
    {
        if (val[i] != 0)
        {
            isPositive = val[i--] > 0;
            break;
        }
    }
 
    if (isPositive)
    {
        for (; i >= 0; --i)
        {
            if (val[i] < 0)
            {
                int k = 0, index = i + 1;
                for (; (size_t)(index) < val.size() && val[index] == 0; ++k, ++index); // count adjacent zeros on left
                //if ((size_t)(index) < val.size() && val[index] > 0)
                { // number on the left is positive
                    val[index] -= 1;
                    val[i] += BASE;
                    for (; k > 0; --k)
                    {
                        val[i + k] = UPPER_BOUND;
                    }
                }
            }
        }
    }
    else
    {
        for (; i >= 0; --i)
        {
            if (val[i] > 0)
            {
                int k = 0, index = i + 1;
                for (; (size_t)(index) < val.size() && val[index] == 0; ++k, ++index); // count adjacent zeros on right
                //if ((size_t)(index) < val.size() && val[index] < 0)
                { // number on the left is negative
                    val[index] += 1;
                    val[i] -= BASE;
                    for (; k > 0; --k)
                    {
                        val[i + k] = -UPPER_BOUND;
                    }
                }
            }
        }
    }
 
    return isPositive;
}
 
inline void InfInt::removeLeadingZeros()
{//PROFILED_SCOPE
    for (int i = (int) (val.size()) - 1; i > 0; --i) // remove leading 0's
    {
        if (val[i] != 0)
        {
            return;
        }
        else
        {
            val.erase(val.begin() + i);
        }
    }
}
 
inline void InfInt::correct(bool justCheckLeadingZeros, bool hasValidSign)
{//PROFILED_SCOPE
    if (!justCheckLeadingZeros)
    {
        truncateToBase();
 
        if (equalizeSigns())
        {
            pos = ((val.size() == 1 && val[0] == 0) || !hasValidSign) ? true : pos;
        }
        else
        {
            pos = hasValidSign ? !pos : false;
            for (size_t i = 0; i < val.size(); ++i)
            {
                val[i] = abs(val[i]);
            }
        }
    }
 
    removeLeadingZeros();
}
 
inline void InfInt::fromString(const std::string& s)
{//PROFILED_SCOPE
    pos = true;
    val.clear();
    // TODO use resize
    val.reserve(s.size() / DIGIT_COUNT + 1);
    int i = (int) s.size() - DIGIT_COUNT;
    for (; i >= 0; i -= DIGIT_COUNT)
    {
        val.push_back(atoi(s.substr(i, DIGIT_COUNT).c_str()));
    }
    if (i > -DIGIT_COUNT)
    {
        std::string ss = s.substr(0, i + DIGIT_COUNT);
        if (ss.size() == 1 && ss[0] == '-')
        {
            pos = false;
        }
        else
        {
            val.push_back(atoi(ss.c_str()));
        }
    }
    if (val.back() < 0)
    {
        val.back() = -val.back();
        pos = false;
    }
    correct(true);
}
 
inline ELEM_TYPE InfInt::dInR(const InfInt& R, const InfInt& D)
{//PROFILED_SCOPE
    ELEM_TYPE min = 0, max = UPPER_BOUND;
    while (max - min > 0)
    {
        ELEM_TYPE avg = max + min;
        //div_t dt = div(avg, 2);
        //avg = dt.rem ? (dt.quot + 1) : dt.quot;
        ELEM_TYPE havg = avg / 2;
        avg = (avg - havg * 2) ? (havg + 1) : havg;
        InfInt prod = D * avg;
        if (R == prod)
        {//PROFILED_SCOPE
            return avg;
        }
        else if (R > prod)
        {//PROFILED_SCOPE
            min = avg;
        }
        else
        {//PROFILED_SCOPE
            max = avg - 1;
        }
    }
    return min;
}
 
inline void InfInt::multiplyByDigit(ELEM_TYPE factor, std::vector<ELEM_TYPE>& val)
{//PROFILED_SCOPE
    ELEM_TYPE carry = 0;
    for (size_t i = 0; i < val.size(); ++i)
    {
        PRODUCT_TYPE pval = val[i] * (PRODUCT_TYPE) factor + carry;
        if (pval >= BASE || pval <= -BASE)
        {
            //carry = (ELEM_TYPE) (pval / BASE);
            //pval %= BASE;
 
            carry = (ELEM_TYPE) (pval / BASE);
            pval -= carry * BASE;
        }
        else
        {
            carry = 0;
        }
        val[i] = (ELEM_TYPE) pval;
    }
    if (carry > 0)
    {
        val.push_back(carry);
    }
}
 
/**************************************************************/
/******************** NON-MEMBER OPERATORS ********************/
/**************************************************************/
 
inline std::istream& operator>>(std::istream &s, InfInt &n)
{//PROFILED_SCOPE
    std::string str;
    s >> str;
    n.fromString(str);
    return s;
}
 
inline std::ostream& operator<<(std::ostream &s, const InfInt &n)
{//PROFILED_SCOPE
    if (!n.pos)
    {
        s << '-';
    }
    bool first = true;
    for (int i = (int) n.val.size() - 1; i >= 0; --i)
    {
        if (first)
        {
            s << n.val[i];
            first = false;
        }
        else
        {
            s << std::setfill('0') << std::setw(DIGIT_COUNT) << n.val[i];
        }
    }
    return s;
}
 
using namespace std;
int main(){
    int a;
    cin >> a;
    InfInt x = 1, kg;
    for (int cont = 0; cont < a; cont++) {
        x *= 2;
    }
    kg = x / 12000;
    cout << kg << " kg\n";
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPGlvbWFuaXA+CgojaW5jbHVkZSA8bGltaXRzLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCgp0eXBlZGVmIGludCBFTEVNX1RZUEU7CnR5cGVkZWYgbG9uZyBsb25nIFBST0RVQ1RfVFlQRTsKc3RhdGljIGNvbnN0IEVMRU1fVFlQRSBCQVNFID0gMTAwMDAwMDAwMDsKc3RhdGljIGNvbnN0IEVMRU1fVFlQRSBVUFBFUl9CT1VORCA9IDk5OTk5OTk5OTsKc3RhdGljIGNvbnN0IEVMRU1fVFlQRSBESUdJVF9DT1VOVCA9IDk7CnN0YXRpYyBjb25zdCBpbnQgcG93ZXJzT2ZUZW5bXSA9IHsgMSwgMTAsIDEwMCwgMTAwMCwgMTAwMDAsIDEwMDAwMCwgMTAwMDAwMCwgMTAwMDAwMDAsIDEwMDAwMDAwMCB9OwpjbGFzcyBJbmZJbnQKewogICAgZnJpZW5kIHN0ZDo6b3N0cmVhbSYgb3BlcmF0b3I8PChzdGQ6Om9zdHJlYW0gJnMsIGNvbnN0IEluZkludCAmbik7CiAgICBmcmllbmQgc3RkOjppc3RyZWFtJiBvcGVyYXRvcj4+KHN0ZDo6aXN0cmVhbSAmcywgSW5mSW50ICZ2YWwpOwoKcHVibGljOgogICAgLyogc29tZSBjb25zdGFudHMgKi8KICAgIHN0YXRpYyBjb25zdCBJbmZJbnQgemVybzsKICAgIHN0YXRpYyBjb25zdCBJbmZJbnQgb25lOwogICAgc3RhdGljIGNvbnN0IEluZkludCB0d287CgogICAgLyogY29uc3RydWN0b3JzICovCiAgICBJbmZJbnQoKTsKICAgIEluZkludChjb25zdCBjaGFyKiBjKTsKICAgIEluZkludChjb25zdCBzdGQ6OnN0cmluZyYgcyk7CiAgICBJbmZJbnQoaW50IGwpOwogICAgSW5mSW50KGxvbmcgbCk7CiAgICBJbmZJbnQobG9uZyBsb25nIGwpOwogICAgSW5mSW50KHVuc2lnbmVkIGludCBsKTsKICAgIEluZkludCh1bnNpZ25lZCBsb25nIGwpOwogICAgSW5mSW50KHVuc2lnbmVkIGxvbmcgbG9uZyBsKTsKCiAgICAvKiBhc3NpZ25tZW50IG9wZXJhdG9ycyAqLwogICAgY29uc3QgSW5mSW50JiBvcGVyYXRvcj0oY29uc3QgY2hhciogYyk7CiAgICBjb25zdCBJbmZJbnQmIG9wZXJhdG9yPShjb25zdCBzdGQ6OnN0cmluZyYgcyk7CiAgICBjb25zdCBJbmZJbnQmIG9wZXJhdG9yPShpbnQgbCk7CiAgICBjb25zdCBJbmZJbnQmIG9wZXJhdG9yPShsb25nIGwpOwogICAgY29uc3QgSW5mSW50JiBvcGVyYXRvcj0obG9uZyBsb25nIGwpOwogICAgY29uc3QgSW5mSW50JiBvcGVyYXRvcj0odW5zaWduZWQgaW50IGwpOwogICAgY29uc3QgSW5mSW50JiBvcGVyYXRvcj0odW5zaWduZWQgbG9uZyBsKTsKICAgIGNvbnN0IEluZkludCYgb3BlcmF0b3I9KHVuc2lnbmVkIGxvbmcgbG9uZyBsKTsKCiAgICAvKiB1bmFyeSBpbmNyZW1lbnQvZGVjcmVtZW50IG9wZXJhdG9ycyAqLwogICAgY29uc3QgSW5mSW50JiBvcGVyYXRvcisrKCk7CiAgICBjb25zdCBJbmZJbnQmIG9wZXJhdG9yLS0oKTsKICAgIEluZkludCBvcGVyYXRvcisrKGludCk7CiAgICBJbmZJbnQgb3BlcmF0b3ItLShpbnQpOwoKICAgIC8qIG9wZXJhdGlvbmFsIGFzc2lnbm1lbnRzICovCiAgICBjb25zdCBJbmZJbnQmIG9wZXJhdG9yKz0oY29uc3QgSW5mSW50JiByaHMpOwogICAgY29uc3QgSW5mSW50JiBvcGVyYXRvci09KGNvbnN0IEluZkludCYgcmhzKTsKICAgIGNvbnN0IEluZkludCYgb3BlcmF0b3IqPShjb25zdCBJbmZJbnQmIHJocyk7CiAgICBjb25zdCBJbmZJbnQmIG9wZXJhdG9yLz0oY29uc3QgSW5mSW50JiByaHMpOyAvLyB0aHJvdwogICAgY29uc3QgSW5mSW50JiBvcGVyYXRvciU9KGNvbnN0IEluZkludCYgcmhzKTsgLy8gdGhyb3cKICAgIGNvbnN0IEluZkludCYgb3BlcmF0b3IqPShFTEVNX1RZUEUgcmhzKTsKCiAgICAvKiBvcGVyYXRpb25zICovCiAgICBJbmZJbnQgb3BlcmF0b3ItKCkgY29uc3Q7CiAgICBJbmZJbnQgb3BlcmF0b3IrKGNvbnN0IEluZkludCYgcmhzKSBjb25zdDsKICAgIEluZkludCBvcGVyYXRvci0oY29uc3QgSW5mSW50JiByaHMpIGNvbnN0OwogICAgSW5mSW50IG9wZXJhdG9yKihjb25zdCBJbmZJbnQmIHJocykgY29uc3Q7CiAgICBJbmZJbnQgb3BlcmF0b3IvKGNvbnN0IEluZkludCYgcmhzKSBjb25zdDsgLy8gdGhyb3cKICAgIEluZkludCBvcGVyYXRvciUoY29uc3QgSW5mSW50JiByaHMpIGNvbnN0OyAvLyB0aHJvdwogICAgSW5mSW50IG9wZXJhdG9yKihFTEVNX1RZUEUgcmhzKSBjb25zdDsKCiAgICAvKiByZWxhdGlvbmFsIG9wZXJhdGlvbnMgKi8KICAgIGJvb2wgb3BlcmF0b3I9PShjb25zdCBJbmZJbnQmIHJocykgY29uc3Q7CiAgICBib29sIG9wZXJhdG9yIT0oY29uc3QgSW5mSW50JiByaHMpIGNvbnN0OwogICAgYm9vbCBvcGVyYXRvcjwoY29uc3QgSW5mSW50JiByaHMpIGNvbnN0OwogICAgYm9vbCBvcGVyYXRvcjw9KGNvbnN0IEluZkludCYgcmhzKSBjb25zdDsKICAgIGJvb2wgb3BlcmF0b3I+KGNvbnN0IEluZkludCYgcmhzKSBjb25zdDsKICAgIGJvb2wgb3BlcmF0b3I+PShjb25zdCBJbmZJbnQmIHJocykgY29uc3Q7CgogICAgLyogaW50ZWdlciBzcXVhcmUgcm9vdCAqLwogICAgSW5mSW50IGludFNxcnQoKSBjb25zdDsgLy8gdGhyb3cKCiAgICAvKiBkaWdpdCBvcGVyYXRpb25zICovCiAgICBjaGFyIGRpZ2l0QXQoc2l6ZV90IGkpIGNvbnN0OyAvLyB0aHJvdwogICAgc2l6ZV90IG51bWJlck9mRGlnaXRzKCkgY29uc3Q7CgogICAgLyogc2l6ZSBpbiBieXRlcyAqLwogICAgc2l6ZV90IHNpemUoKSBjb25zdDsKCiAgICAvKiBzdHJpbmcgY29udmVyc2lvbiAqLwogICAgc3RkOjpzdHJpbmcgdG9TdHJpbmcoKSBjb25zdDsKCiAgICAvKiBjb252ZXJzaW9uIHRvIHByaW1pdGl2ZSB0eXBlcyAqLwogICAgaW50IHRvSW50KCkgY29uc3Q7IC8vIHRocm93CiAgICBsb25nIHRvTG9uZygpIGNvbnN0OyAvLyB0aHJvdwogICAgbG9uZyBsb25nIHRvTG9uZ0xvbmcoKSBjb25zdDsgLy8gdGhyb3cKICAgIHVuc2lnbmVkIGludCB0b1Vuc2lnbmVkSW50KCkgY29uc3Q7IC8vIHRocm93CiAgICB1bnNpZ25lZCBsb25nIHRvVW5zaWduZWRMb25nKCkgY29uc3Q7IC8vIHRocm93CiAgICB1bnNpZ25lZCBsb25nIGxvbmcgdG9VbnNpZ25lZExvbmdMb25nKCkgY29uc3Q7IC8vIHRocm93Cgpwcml2YXRlOgogICAgc3RhdGljIEVMRU1fVFlQRSBkSW5SKGNvbnN0IEluZkludCYgUiwgY29uc3QgSW5mSW50JiBEKTsKICAgIHN0YXRpYyB2b2lkIG11bHRpcGx5QnlEaWdpdChFTEVNX1RZUEUgZmFjdG9yLCBzdGQ6OnZlY3RvcjxFTEVNX1RZUEU+JiB2YWwpOwoKICAgIHZvaWQgY29ycmVjdChib29sIGp1c3RDaGVja0xlYWRpbmdaZXJvcyA9IGZhbHNlLCBib29sIGhhc1ZhbGlkU2lnbiA9IGZhbHNlKTsKICAgIHZvaWQgZnJvbVN0cmluZyhjb25zdCBzdGQ6OnN0cmluZyYgcyk7CiAgICB2b2lkIG9wdGltaXplU3FydFNlYXJjaEJvdW5kcyhJbmZJbnQmIGxvLCBJbmZJbnQmIGhpKSBjb25zdDsKICAgIHZvaWQgdHJ1bmNhdGVUb0Jhc2UoKTsKICAgIGJvb2wgZXF1YWxpemVTaWducygpOwogICAgdm9pZCByZW1vdmVMZWFkaW5nWmVyb3MoKTsKCiAgICBzdGQ6OnZlY3RvcjxFTEVNX1RZUEU+IHZhbDsgLy8gbnVtYmVyIHdpdGggYmFzZSBGQUNUT1IKICAgIGJvb2wgcG9zOyAvLyB0cnVlIGlmIG51bWJlciBpcyBwb3NpdGl2ZQp9OwoKY29uc3QgSW5mSW50IEluZkludDo6emVybyA9IDA7CmNvbnN0IEluZkludCBJbmZJbnQ6Om9uZSA9IDE7CmNvbnN0IEluZkludCBJbmZJbnQ6OnR3byA9IDI7CgppbmxpbmUgSW5mSW50OjpJbmZJbnQoKSA6IHBvcyh0cnVlKQp7CiAgICB2YWwucHVzaF9iYWNrKChFTEVNX1RZUEUpIDApOwp9CgppbmxpbmUgSW5mSW50OjpJbmZJbnQoY29uc3QgY2hhciogYykKewogICAgZnJvbVN0cmluZyhjKTsKfQoKaW5saW5lIEluZkludDo6SW5mSW50KGNvbnN0IHN0ZDo6c3RyaW5nJiBzKQp7CiAgICBmcm9tU3RyaW5nKHMpOwp9CgppbmxpbmUgSW5mSW50OjpJbmZJbnQoaW50IGwpIDogcG9zKGwgPj0gMCkKewogICAgaWYgKCFwb3MpCiAgICB7CiAgICAgICAgbCA9IC1sOwogICAgfQogICAgZG8KICAgIHsKICAgICAgICBkaXZfdCBkdCA9IGRpdihsLCBCQVNFKTsKICAgICAgICB2YWwucHVzaF9iYWNrKChFTEVNX1RZUEUpIGR0LnJlbSk7CiAgICAgICAgbCA9IGR0LnF1b3Q7CiAgICB9IHdoaWxlIChsID4gMCk7Cn0KCmlubGluZSBJbmZJbnQ6OkluZkludChsb25nIGwpIDogcG9zKGwgPj0gMCkKewogICAgaWYgKCFwb3MpCiAgICB7CiAgICAgICAgbCA9IC1sOwogICAgfQogICAgZG8KICAgIHsKICAgICAgICBsZGl2X3QgZHQgPSBsZGl2KGwsIEJBU0UpOwogICAgICAgIHZhbC5wdXNoX2JhY2soKEVMRU1fVFlQRSkgZHQucmVtKTsKICAgICAgICBsID0gZHQucXVvdDsKICAgIH0gd2hpbGUgKGwgPiAwKTsKfQoKaW5saW5lIEluZkludDo6SW5mSW50KGxvbmcgbG9uZyBsKSA6IHBvcyhsID49IDApCnsKICAgIGlmICghcG9zKQogICAgewogICAgICAgIGwgPSAtbDsKICAgIH0KICAgIGRvCiAgICB7CiAgICAgICAgdmFsLnB1c2hfYmFjaygoRUxFTV9UWVBFKSAobCAlIEJBU0UpKTsKICAgICAgICBsID0gbCAvIEJBU0U7CiAgICB9IHdoaWxlIChsID4gMCk7Cn0KCmlubGluZSBJbmZJbnQ6OkluZkludCh1bnNpZ25lZCBpbnQgbCkgOiBwb3ModHJ1ZSkKewogICAgZG8KICAgIHsKICAgICAgICB2YWwucHVzaF9iYWNrKChFTEVNX1RZUEUpIChsICUgQkFTRSkpOwogICAgICAgIGwgPSBsIC8gQkFTRTsKICAgIH0gd2hpbGUgKGwgPiAwKTsKfQoKaW5saW5lIEluZkludDo6SW5mSW50KHVuc2lnbmVkIGxvbmcgbCkgOiBwb3ModHJ1ZSkKewogICAgZG8KICAgIHsKICAgICAgICB2YWwucHVzaF9iYWNrKChFTEVNX1RZUEUpIChsICUgQkFTRSkpOwogICAgICAgIGwgPSBsIC8gQkFTRTsKICAgIH0gd2hpbGUgKGwgPiAwKTsKfQoKaW5saW5lIEluZkludDo6SW5mSW50KHVuc2lnbmVkIGxvbmcgbG9uZyBsKSA6IHBvcyh0cnVlKQp7CiAgICBkbwogICAgewogICAgICAgIHZhbC5wdXNoX2JhY2soKEVMRU1fVFlQRSkgKGwgJSBCQVNFKSk7CiAgICAgICAgbCA9IGwgLyBCQVNFOwogICAgfSB3aGlsZSAobCA+IDApOwp9CgppbmxpbmUgY29uc3QgSW5mSW50JiBJbmZJbnQ6Om9wZXJhdG9yPShjb25zdCBjaGFyKiBjKQp7CiAgICBmcm9tU3RyaW5nKGMpOwogICAgcmV0dXJuICp0aGlzOwp9CgppbmxpbmUgY29uc3QgSW5mSW50JiBJbmZJbnQ6Om9wZXJhdG9yPShjb25zdCBzdGQ6OnN0cmluZyYgcykKewogICAgZnJvbVN0cmluZyhzKTsKICAgIHJldHVybiAqdGhpczsKfQoKaW5saW5lIGNvbnN0IEluZkludCYgSW5mSW50OjpvcGVyYXRvcj0oaW50IGwpCnsKICAgIHBvcyA9IGwgPj0gMDsKICAgIHZhbC5jbGVhcigpOwogICAgaWYgKCFwb3MpCiAgICB7CiAgICAgICAgbCA9IC1sOwogICAgfQogICAgZG8KICAgIHsKICAgICAgICBkaXZfdCBkdCA9IGRpdihsLCBCQVNFKTsKICAgICAgICB2YWwucHVzaF9iYWNrKChFTEVNX1RZUEUpIGR0LnJlbSk7CiAgICAgICAgbCA9IGR0LnF1b3Q7CiAgICB9IHdoaWxlIChsID4gMCk7CiAgICByZXR1cm4gKnRoaXM7Cn0KCmlubGluZSBjb25zdCBJbmZJbnQmIEluZkludDo6b3BlcmF0b3I9KGxvbmcgbCkKewogICAgcG9zID0gbCA+PSAwOwogICAgdmFsLmNsZWFyKCk7CiAgICBpZiAoIXBvcykKICAgIHsKICAgICAgICBsID0gLWw7CiAgICB9CiAgICBkbwogICAgewogICAgICAgIGxkaXZfdCBkdCA9IGxkaXYobCwgQkFTRSk7CiAgICAgICAgdmFsLnB1c2hfYmFjaygoRUxFTV9UWVBFKSBkdC5yZW0pOwogICAgICAgIGwgPSBkdC5xdW90OwogICAgfSB3aGlsZSAobCA+IDApOwogICAgcmV0dXJuICp0aGlzOwp9CgppbmxpbmUgY29uc3QgSW5mSW50JiBJbmZJbnQ6Om9wZXJhdG9yPShsb25nIGxvbmcgbCkKewogICAgcG9zID0gbCA+PSAwOwogICAgdmFsLmNsZWFyKCk7CiAgICBpZiAoIXBvcykKICAgIHsKICAgICAgICBsID0gLWw7CiAgICB9CiAgICBkbwogICAgewogICAgICAgIHZhbC5wdXNoX2JhY2soKEVMRU1fVFlQRSkgKGwgJSBCQVNFKSk7CiAgICAgICAgbCA9IGwgLyBCQVNFOwogICAgfSB3aGlsZSAobCA+IDApOwogICAgcmV0dXJuICp0aGlzOwp9CgppbmxpbmUgY29uc3QgSW5mSW50JiBJbmZJbnQ6Om9wZXJhdG9yPSh1bnNpZ25lZCBpbnQgbCkKewogICAgcG9zID0gdHJ1ZTsKICAgIHZhbC5jbGVhcigpOwogICAgZG8KICAgIHsKICAgICAgICB2YWwucHVzaF9iYWNrKChFTEVNX1RZUEUpIChsICUgQkFTRSkpOwogICAgICAgIGwgPSBsIC8gQkFTRTsKICAgIH0gd2hpbGUgKGwgPiAwKTsKICAgIHJldHVybiAqdGhpczsKfQoKaW5saW5lIGNvbnN0IEluZkludCYgSW5mSW50OjpvcGVyYXRvcj0odW5zaWduZWQgbG9uZyBsKQp7CiAgICBwb3MgPSB0cnVlOwogICAgdmFsLmNsZWFyKCk7CiAgICBkbwogICAgewogICAgICAgIHZhbC5wdXNoX2JhY2soKEVMRU1fVFlQRSkgKGwgJSBCQVNFKSk7CiAgICAgICAgbCA9IGwgLyBCQVNFOwogICAgfSB3aGlsZSAobCA+IDApOwogICAgcmV0dXJuICp0aGlzOwp9CgppbmxpbmUgY29uc3QgSW5mSW50JiBJbmZJbnQ6Om9wZXJhdG9yPSh1bnNpZ25lZCBsb25nIGxvbmcgbCkKewogICAgcG9zID0gdHJ1ZTsKICAgIHZhbC5jbGVhcigpOwogICAgZG8KICAgIHsKICAgICAgICB2YWwucHVzaF9iYWNrKChFTEVNX1RZUEUpIChsICUgQkFTRSkpOwogICAgICAgIGwgPSBsIC8gQkFTRTsKICAgIH0gd2hpbGUgKGwgPiAwKTsKICAgIHJldHVybiAqdGhpczsKfQoKaW5saW5lIGNvbnN0IEluZkludCYgSW5mSW50OjpvcGVyYXRvcisrKCkKewogICAgdmFsWzBdICs9IChwb3MgPyAxIDogLTEpOwogICAgdGhpcy0+Y29ycmVjdChmYWxzZSwgdHJ1ZSk7CiAgICByZXR1cm4gKnRoaXM7Cn0KCmlubGluZSBjb25zdCBJbmZJbnQmIEluZkludDo6b3BlcmF0b3ItLSgpCnsKICAgIHZhbFswXSAtPSAocG9zID8gMSA6IC0xKTsKICAgIHRoaXMtPmNvcnJlY3QoZmFsc2UsIHRydWUpOwogICAgcmV0dXJuICp0aGlzOwp9CgppbmxpbmUgSW5mSW50IEluZkludDo6b3BlcmF0b3IrKyhpbnQpCnsKICAgIEluZkludCByZXN1bHQgPSAqdGhpczsKICAgIHZhbFswXSArPSAocG9zID8gMSA6IC0xKTsKICAgIHRoaXMtPmNvcnJlY3QoZmFsc2UsIHRydWUpOwogICAgcmV0dXJuIHJlc3VsdDsKfQoKaW5saW5lIEluZkludCBJbmZJbnQ6Om9wZXJhdG9yLS0oaW50KQp7CiAgICBJbmZJbnQgcmVzdWx0ID0gKnRoaXM7CiAgICB2YWxbMF0gLT0gKHBvcyA/IDEgOiAtMSk7CiAgICB0aGlzLT5jb3JyZWN0KGZhbHNlLCB0cnVlKTsKICAgIHJldHVybiByZXN1bHQ7Cn0KCmlubGluZSBjb25zdCBJbmZJbnQmIEluZkludDo6b3BlcmF0b3IrPShjb25zdCBJbmZJbnQmIHJocykKewogICAgaWYgKHJocy52YWwuc2l6ZSgpID4gdmFsLnNpemUoKSkKICAgIHsKICAgICAgICB2YWwucmVzaXplKHJocy52YWwuc2l6ZSgpLCAwKTsKICAgIH0KICAgIGZvciAoc2l6ZV90IGkgPSAwOyBpIDwgdmFsLnNpemUoKTsgKytpKQogICAgewogICAgICAgIHZhbFtpXSA9IChwb3MgPyB2YWxbaV0gOiAtdmFsW2ldKSArIChpIDwgcmhzLnZhbC5zaXplKCkgPyAocmhzLnBvcyA/IHJocy52YWxbaV0gOiAtcmhzLnZhbFtpXSkgOiAwKTsKICAgIH0KICAgIGNvcnJlY3QoKTsKICAgIHJldHVybiAqdGhpczsKfQoKaW5saW5lIGNvbnN0IEluZkludCYgSW5mSW50OjpvcGVyYXRvci09KGNvbnN0IEluZkludCYgcmhzKQp7CiAgICBpZiAocmhzLnZhbC5zaXplKCkgPiB2YWwuc2l6ZSgpKQogICAgewogICAgICAgIHZhbC5yZXNpemUocmhzLnZhbC5zaXplKCksIDApOwogICAgfQogICAgZm9yIChzaXplX3QgaSA9IDA7IGkgPCB2YWwuc2l6ZSgpOyArK2kpCiAgICB7CiAgICAgICAgdmFsW2ldID0gKHBvcyA/IHZhbFtpXSA6IC12YWxbaV0pIC0gKGkgPCByaHMudmFsLnNpemUoKSA/IChyaHMucG9zID8gcmhzLnZhbFtpXSA6IC1yaHMudmFsW2ldKSA6IDApOwogICAgfQogICAgY29ycmVjdCgpOwogICAgcmV0dXJuICp0aGlzOwp9CgppbmxpbmUgY29uc3QgSW5mSW50JiBJbmZJbnQ6Om9wZXJhdG9yKj0oY29uc3QgSW5mSW50JiByaHMpCnsKICAgIC8vIFRPRE86IG9wdGltaXplIChkbyBub3QgdXNlIG9wZXJhdG9yKikKICAgICp0aGlzID0gKnRoaXMgKiByaHM7CiAgICByZXR1cm4gKnRoaXM7Cn0KCmlubGluZSBjb25zdCBJbmZJbnQmIEluZkludDo6b3BlcmF0b3IvPShjb25zdCBJbmZJbnQmIHJocykKewogICAgaWYgKHJocyA9PSB6ZXJvKQogICAgewogICAgICAgIHN0ZDo6Y2VyciA8PCAiRGl2aXNpb24gYnkgemVybyEiIDw8IHN0ZDo6ZW5kbDsKICAgICAgICByZXR1cm4gKnRoaXM7CiAgICB9CiAgICBJbmZJbnQgUiwgRCA9IChyaHMucG9zID8gcmhzIDogLXJocyksIE4gPSAocG9zID8gKnRoaXMgOiAtKnRoaXMpOwogICAgYm9vbCBvbGRwb3MgPSBwb3M7CiAgICB2YWwuY2xlYXIoKTsKICAgIHZhbC5yZXNpemUoTi52YWwuc2l6ZSgpLCAwKTsKICAgIGZvciAoaW50IGkgPSAoaW50KSBOLnZhbC5zaXplKCkgLSAxOyBpID49IDA7IC0taSkKICAgIHsKICAgICAgICBSLnZhbC5pbnNlcnQoUi52YWwuYmVnaW4oKSwgKEVMRU1fVFlQRSkgMCk7CiAgICAgICAgUi52YWxbMF0gPSBOLnZhbFtpXTsKICAgICAgICBSLmNvcnJlY3QodHJ1ZSk7CiAgICAgICAgRUxFTV9UWVBFIGNudCA9IGRJblIoUiwgRCk7CiAgICAgICAgUiAtPSBEICogY250OwogICAgICAgIHZhbFtpXSArPSBjbnQ7CiAgICB9CiAgICBjb3JyZWN0KCk7CiAgICBwb3MgPSAodmFsLnNpemUoKSA9PSAxICYmIHZhbFswXSA9PSAwKSA/IHRydWUgOiAob2xkcG9zID09IHJocy5wb3MpOwogICAgcmV0dXJuICp0aGlzOwp9CgppbmxpbmUgY29uc3QgSW5mSW50JiBJbmZJbnQ6Om9wZXJhdG9yJT0oY29uc3QgSW5mSW50JiByaHMpCnsKICAgIGlmIChyaHMgPT0gemVybykKICAgIHsKICAgICAgICBzdGQ6OmNlcnIgPDwgIkRpdmlzaW9uIGJ5IHplcm8hIiA8PCBzdGQ6OmVuZGw7CiAgICAgICAgcmV0dXJuIHplcm87CiAgICB9CiAgICBJbmZJbnQgRCA9IChyaHMucG9zID8gcmhzIDogLXJocyksIE4gPSAocG9zID8gKnRoaXMgOiAtKnRoaXMpOwogICAgYm9vbCBvbGRwb3MgPSBwb3M7CiAgICB2YWwuY2xlYXIoKTsKICAgIGZvciAoaW50IGkgPSAoaW50KSBOLnZhbC5zaXplKCkgLSAxOyBpID49IDA7IC0taSkKICAgIHsKICAgICAgICB2YWwuaW5zZXJ0KHZhbC5iZWdpbigpLCAoRUxFTV9UWVBFKSAwKTsKICAgICAgICB2YWxbMF0gPSBOLnZhbFtpXTsKICAgICAgICBjb3JyZWN0KHRydWUpOwogICAgICAgICp0aGlzIC09IEQgKiBkSW5SKCp0aGlzLCBEKTsKICAgIH0KICAgIGNvcnJlY3QoKTsKICAgIHBvcyA9ICh2YWwuc2l6ZSgpID09IDEgJiYgdmFsWzBdID09IDApID8gdHJ1ZSA6IG9sZHBvczsKICAgIHJldHVybiAqdGhpczsKfQoKaW5saW5lIGNvbnN0IEluZkludCYgSW5mSW50OjpvcGVyYXRvcio9KEVMRU1fVFlQRSByaHMpCnsKICAgIEVMRU1fVFlQRSBmYWN0b3IgPSByaHMgPCAwID8gLXJocyA6IHJoczsKICAgIGJvb2wgb2xkcG9zID0gcG9zOwogICAgbXVsdGlwbHlCeURpZ2l0KGZhY3RvciwgdmFsKTsKICAgIGNvcnJlY3QoKTsKICAgIHBvcyA9ICh2YWwuc2l6ZSgpID09IDEgJiYgdmFsWzBdID09IDApID8gdHJ1ZSA6IChvbGRwb3MgPT0gKHJocyA+PSAwKSk7CiAgICByZXR1cm4gKnRoaXM7Cn0KCmlubGluZSBJbmZJbnQgSW5mSW50OjpvcGVyYXRvci0oKSBjb25zdAp7Ly9QUk9GSUxFRF9TQ09QRQogICAgSW5mSW50IHJlc3VsdCA9ICp0aGlzOwogICAgcmVzdWx0LnBvcyA9ICFwb3M7CiAgICByZXR1cm4gcmVzdWx0Owp9CgppbmxpbmUgSW5mSW50IEluZkludDo6b3BlcmF0b3IrKGNvbnN0IEluZkludCYgcmhzKSBjb25zdAp7Ly9QUk9GSUxFRF9TQ09QRQogICAgSW5mSW50IHJlc3VsdDsKICAgIHJlc3VsdC52YWwucmVzaXplKHZhbC5zaXplKCkgPiByaHMudmFsLnNpemUoKSA/IHZhbC5zaXplKCkgOiByaHMudmFsLnNpemUoKSwgMCk7CiAgICBmb3IgKHNpemVfdCBpID0gMDsgaSA8IHZhbC5zaXplKCkgfHwgaSA8IHJocy52YWwuc2l6ZSgpOyArK2kpCiAgICB7CiAgICAgICAgcmVzdWx0LnZhbFtpXSA9IChpIDwgdmFsLnNpemUoKSA/IChwb3MgPyB2YWxbaV0gOiAtdmFsW2ldKSA6IDApICsgKGkgPCByaHMudmFsLnNpemUoKSA/IChyaHMucG9zID8gcmhzLnZhbFtpXSA6IC1yaHMudmFsW2ldKSA6IDApOwogICAgfQogICAgcmVzdWx0LmNvcnJlY3QoKTsKICAgIHJldHVybiByZXN1bHQ7Cn0KCmlubGluZSBJbmZJbnQgSW5mSW50OjpvcGVyYXRvci0oY29uc3QgSW5mSW50JiByaHMpIGNvbnN0CnsvL1BST0ZJTEVEX1NDT1BFCiAgICBJbmZJbnQgcmVzdWx0OwogICAgcmVzdWx0LnZhbC5yZXNpemUodmFsLnNpemUoKSA+IHJocy52YWwuc2l6ZSgpID8gdmFsLnNpemUoKSA6IHJocy52YWwuc2l6ZSgpLCAwKTsKICAgIGZvciAoc2l6ZV90IGkgPSAwOyBpIDwgdmFsLnNpemUoKSB8fCBpIDwgcmhzLnZhbC5zaXplKCk7ICsraSkKICAgIHsKICAgICAgICByZXN1bHQudmFsW2ldID0gKGkgPCB2YWwuc2l6ZSgpID8gKHBvcyA/IHZhbFtpXSA6IC12YWxbaV0pIDogMCkgLSAoaSA8IHJocy52YWwuc2l6ZSgpID8gKHJocy5wb3MgPyByaHMudmFsW2ldIDogLXJocy52YWxbaV0pIDogMCk7CiAgICB9CiAgICByZXN1bHQuY29ycmVjdCgpOwogICAgcmV0dXJuIHJlc3VsdDsKfQoKaW5saW5lIEluZkludCBJbmZJbnQ6Om9wZXJhdG9yKihjb25zdCBJbmZJbnQmIHJocykgY29uc3QKey8vUFJPRklMRURfU0NPUEUKICAgIEluZkludCByZXN1bHQ7CiAgICByZXN1bHQudmFsLnJlc2l6ZSh2YWwuc2l6ZSgpICsgcmhzLnZhbC5zaXplKCksIDApOwogICAgUFJPRFVDVF9UWVBFIGNhcnJ5ID0gMDsKICAgIHNpemVfdCBkaWdpdCA9IDA7CiAgICBmb3IgKDs7ICsrZGlnaXQpCiAgICB7Ly9QUk9GSUxFRF9TQ09QRQogICAgICAgIC8vcmVzdWx0LnZhbFtkaWdpdF0gPSAoRUxFTV9UWVBFKSAoY2FycnkgJSBCQVNFKTsKICAgICAgICAvL2NhcnJ5IC89IEJBU0U7CgogICAgICAgIFBST0RVQ1RfVFlQRSBvbGRjYXJyeSA9IGNhcnJ5OwogICAgICAgIGNhcnJ5IC89IEJBU0U7CiAgICAgICAgcmVzdWx0LnZhbFtkaWdpdF0gPSAoRUxFTV9UWVBFKSAob2xkY2FycnkgLSBjYXJyeSAqIEJBU0UpOwoKICAgICAgICBib29sIGZvdW5kID0gZmFsc2U7CiAgICAgICAgZm9yIChzaXplX3QgaSA9IGRpZ2l0IDwgcmhzLnZhbC5zaXplKCkgPyAwIDogZGlnaXQgLSByaHMudmFsLnNpemUoKSArIDE7IGkgPCB2YWwuc2l6ZSgpICYmIGkgPD0gZGlnaXQ7ICsraSkKICAgICAgICB7Ly9QUk9GSUxFRF9TQ09QRQogICAgICAgICAgICBQUk9EVUNUX1RZUEUgcHZhbCA9IHJlc3VsdC52YWxbZGlnaXRdICsgdmFsW2ldICogKFBST0RVQ1RfVFlQRSkgcmhzLnZhbFtkaWdpdCAtIGldOwogICAgICAgICAgICBpZiAocHZhbCA+PSBCQVNFIHx8IHB2YWwgPD0gLUJBU0UpCiAgICAgICAgICAgIHsvL1BST0ZJTEVEX1NDT1BFCiAgICAgICAgICAgICAgICAvL2NhcnJ5ICs9IHB2YWwgLyBCQVNFOwogICAgICAgICAgICAgICAgLy9wdmFsICU9IEJBU0U7CgogICAgICAgICAgICAgICAgUFJPRFVDVF9UWVBFIHF1b3QgPSBwdmFsIC8gQkFTRTsKICAgICAgICAgICAgICAgIGNhcnJ5ICs9IHF1b3Q7CiAgICAgICAgICAgICAgICBwdmFsIC09IHF1b3QgKiBCQVNFOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHJlc3VsdC52YWxbZGlnaXRdID0gKEVMRU1fVFlQRSkgcHZhbDsKICAgICAgICAgICAgZm91bmQgPSB0cnVlOwogICAgICAgIH0KICAgICAgICBpZiAoIWZvdW5kKQogICAgICAgIHsvL1BST0ZJTEVEX1NDT1BFCiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgIH0KICAgIGZvciAoOyBjYXJyeSA+IDA7ICsrZGlnaXQpCiAgICB7Ly9QUk9GSUxFRF9TQ09QRQogICAgICAgIHJlc3VsdC52YWxbZGlnaXRdID0gKEVMRU1fVFlQRSkgKGNhcnJ5ICUgQkFTRSk7CiAgICAgICAgY2FycnkgLz0gQkFTRTsKICAgIH0KICAgIHJlc3VsdC5jb3JyZWN0KCk7CiAgICByZXN1bHQucG9zID0gKHJlc3VsdC52YWwuc2l6ZSgpID09IDEgJiYgcmVzdWx0LnZhbFswXSA9PSAwKSA/IHRydWUgOiAocG9zID09IHJocy5wb3MpOwogICAgcmV0dXJuIHJlc3VsdDsKfQoKaW5saW5lIEluZkludCBJbmZJbnQ6Om9wZXJhdG9yLyhjb25zdCBJbmZJbnQmIHJocykgY29uc3QKey8vUFJPRklMRURfU0NPUEUKICAgIGlmIChyaHMgPT0gemVybykKICAgIHsKICAgICAgICBzdGQ6OmNlcnIgPDwgIkRpdmlzaW9uIGJ5IHplcm8hIiA8PCBzdGQ6OmVuZGw7CiAgICAgICAgcmV0dXJuIHplcm87CiAgICB9CiAgICBJbmZJbnQgUSwgUiwgRCA9IChyaHMucG9zID8gcmhzIDogLXJocyksIE4gPSAocG9zID8gKnRoaXMgOiAtKnRoaXMpOwogICAgUS52YWwucmVzaXplKE4udmFsLnNpemUoKSwgMCk7CiAgICBmb3IgKGludCBpID0gKGludCkgTi52YWwuc2l6ZSgpIC0gMTsgaSA+PSAwOyAtLWkpCiAgICB7Ly9QUk9GSUxFRF9TQ09QRQogICAgICAgIFIudmFsLmluc2VydChSLnZhbC5iZWdpbigpLCAoRUxFTV9UWVBFKSAwKTsKICAgICAgICBSLnZhbFswXSA9IE4udmFsW2ldOwogICAgICAgIFIuY29ycmVjdCh0cnVlKTsKICAgICAgICBFTEVNX1RZUEUgY250ID0gZEluUihSLCBEKTsKICAgICAgICBSIC09IEQgKiBjbnQ7CiAgICAgICAgUS52YWxbaV0gKz0gY250OwogICAgfQogICAgUS5jb3JyZWN0KCk7CiAgICBRLnBvcyA9IChRLnZhbC5zaXplKCkgPT0gMSAmJiBRLnZhbFswXSA9PSAwKSA/IHRydWUgOiAocG9zID09IHJocy5wb3MpOwogICAgcmV0dXJuIFE7Cn0KCmlubGluZSBJbmZJbnQgSW5mSW50OjpvcGVyYXRvciUoY29uc3QgSW5mSW50JiByaHMpIGNvbnN0CnsvL1BST0ZJTEVEX1NDT1BFCiAgICBpZiAocmhzID09IHplcm8pCiAgICB7CiAgICAgICAgc3RkOjpjZXJyIDw8ICJEaXZpc2lvbiBieSB6ZXJvISIgPDwgc3RkOjplbmRsOwogICAgICAgIHJldHVybiB6ZXJvOwogICAgfQogICAgSW5mSW50IFIsIEQgPSAocmhzLnBvcyA/IHJocyA6IC1yaHMpLCBOID0gKHBvcyA/ICp0aGlzIDogLSp0aGlzKTsKICAgIGZvciAoaW50IGkgPSAoaW50KSBOLnZhbC5zaXplKCkgLSAxOyBpID49IDA7IC0taSkKICAgIHsKICAgICAgICBSLnZhbC5pbnNlcnQoUi52YWwuYmVnaW4oKSwgKEVMRU1fVFlQRSkgMCk7CiAgICAgICAgUi52YWxbMF0gPSBOLnZhbFtpXTsKICAgICAgICBSLmNvcnJlY3QodHJ1ZSk7CiAgICAgICAgUiAtPSBEICogZEluUihSLCBEKTsKICAgIH0KICAgIFIuY29ycmVjdCgpOwogICAgUi5wb3MgPSAoUi52YWwuc2l6ZSgpID09IDEgJiYgUi52YWxbMF0gPT0gMCkgPyB0cnVlIDogcG9zOwogICAgcmV0dXJuIFI7Cn0KCmlubGluZSBJbmZJbnQgSW5mSW50OjpvcGVyYXRvciooRUxFTV9UWVBFIHJocykgY29uc3QKey8vUFJPRklMRURfU0NPUEUKICAgIEluZkludCByZXN1bHQgPSAqdGhpczsKICAgIEVMRU1fVFlQRSBmYWN0b3IgPSByaHMgPCAwID8gLXJocyA6IHJoczsKICAgIG11bHRpcGx5QnlEaWdpdChmYWN0b3IsIHJlc3VsdC52YWwpOwogICAgcmVzdWx0LmNvcnJlY3QoKTsKICAgIHJlc3VsdC5wb3MgPSAocmVzdWx0LnZhbC5zaXplKCkgPT0gMSAmJiByZXN1bHQudmFsWzBdID09IDApID8gdHJ1ZSA6IChwb3MgPT0gKHJocyA+PSAwKSk7CiAgICByZXR1cm4gcmVzdWx0Owp9CgppbmxpbmUgYm9vbCBJbmZJbnQ6Om9wZXJhdG9yPT0oY29uc3QgSW5mSW50JiByaHMpIGNvbnN0CnsvL1BST0ZJTEVEX1NDT1BFCiAgICBpZiAocG9zICE9IHJocy5wb3MgfHwgdmFsLnNpemUoKSAhPSByaHMudmFsLnNpemUoKSkKICAgIHsKICAgICAgICByZXR1cm4gZmFsc2U7CiAgICB9CiAgICBmb3IgKGludCBpID0gKGludCkgdmFsLnNpemUoKSAtIDE7IGkgPj0gMDsgLS1pKQogICAgewogICAgICAgIGlmICh2YWxbaV0gIT0gcmhzLnZhbFtpXSkKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gdHJ1ZTsKfQoKaW5saW5lIGJvb2wgSW5mSW50OjpvcGVyYXRvciE9KGNvbnN0IEluZkludCYgcmhzKSBjb25zdAp7Ly9QUk9GSUxFRF9TQ09QRQogICAgaWYgKHBvcyAhPSByaHMucG9zIHx8IHZhbC5zaXplKCkgIT0gcmhzLnZhbC5zaXplKCkpCiAgICB7CiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9CiAgICBmb3IgKGludCBpID0gKGludCkgdmFsLnNpemUoKSAtIDE7IGkgPj0gMDsgLS1pKQogICAgewogICAgICAgIGlmICh2YWxbaV0gIT0gcmhzLnZhbFtpXSkKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiB0cnVlOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBmYWxzZTsKfQoKaW5saW5lIGJvb2wgSW5mSW50OjpvcGVyYXRvcjwoY29uc3QgSW5mSW50JiByaHMpIGNvbnN0CnsvL1BST0ZJTEVEX1NDT1BFCiAgICBpZiAocG9zICYmICFyaHMucG9zKQogICAgewogICAgICAgIHJldHVybiBmYWxzZTsKICAgIH0KICAgIGlmICghcG9zICYmIHJocy5wb3MpCiAgICB7CiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9CiAgICBpZiAodmFsLnNpemUoKSA+IHJocy52YWwuc2l6ZSgpKQogICAgewogICAgICAgIHJldHVybiBwb3MgPyBmYWxzZSA6IHRydWU7CiAgICB9CiAgICBpZiAodmFsLnNpemUoKSA8IHJocy52YWwuc2l6ZSgpKQogICAgewogICAgICAgIHJldHVybiBwb3MgPyB0cnVlIDogZmFsc2U7CiAgICB9CiAgICBmb3IgKGludCBpID0gKGludCkgdmFsLnNpemUoKSAtIDE7IGkgPj0gMDsgLS1pKQogICAgewogICAgICAgIGlmICh2YWxbaV0gPCByaHMudmFsW2ldKQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIHBvcyA/IHRydWUgOiBmYWxzZTsKICAgICAgICB9CiAgICAgICAgaWYgKHZhbFtpXSA+IHJocy52YWxbaV0pCiAgICAgICAgewogICAgICAgICAgICByZXR1cm4gcG9zID8gZmFsc2UgOiB0cnVlOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBmYWxzZTsKfQoKaW5saW5lIGJvb2wgSW5mSW50OjpvcGVyYXRvcjw9KGNvbnN0IEluZkludCYgcmhzKSBjb25zdAp7Ly9QUk9GSUxFRF9TQ09QRQogICAgaWYgKHBvcyAmJiAhcmhzLnBvcykKICAgIHsKICAgICAgICByZXR1cm4gZmFsc2U7CiAgICB9CiAgICBpZiAoIXBvcyAmJiByaHMucG9zKQogICAgewogICAgICAgIHJldHVybiB0cnVlOwogICAgfQogICAgaWYgKHZhbC5zaXplKCkgPiByaHMudmFsLnNpemUoKSkKICAgIHsKICAgICAgICByZXR1cm4gcG9zID8gZmFsc2UgOiB0cnVlOwogICAgfQogICAgaWYgKHZhbC5zaXplKCkgPCByaHMudmFsLnNpemUoKSkKICAgIHsKICAgICAgICByZXR1cm4gcG9zID8gdHJ1ZSA6IGZhbHNlOwogICAgfQogICAgZm9yIChpbnQgaSA9IChpbnQpIHZhbC5zaXplKCkgLSAxOyBpID49IDA7IC0taSkKICAgIHsKICAgICAgICBpZiAodmFsW2ldIDwgcmhzLnZhbFtpXSkKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiBwb3MgPyB0cnVlIDogZmFsc2U7CiAgICAgICAgfQogICAgICAgIGlmICh2YWxbaV0gPiByaHMudmFsW2ldKQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIHBvcyA/IGZhbHNlIDogdHJ1ZTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gdHJ1ZTsKfQoKaW5saW5lIGJvb2wgSW5mSW50OjpvcGVyYXRvcj4oY29uc3QgSW5mSW50JiByaHMpIGNvbnN0CnsvL1BST0ZJTEVEX1NDT1BFCiAgICBpZiAocG9zICYmICFyaHMucG9zKQogICAgewogICAgICAgIHJldHVybiB0cnVlOwogICAgfQogICAgaWYgKCFwb3MgJiYgcmhzLnBvcykKICAgIHsKICAgICAgICByZXR1cm4gZmFsc2U7CiAgICB9CiAgICBpZiAodmFsLnNpemUoKSA+IHJocy52YWwuc2l6ZSgpKQogICAgewogICAgICAgIHJldHVybiBwb3MgPyB0cnVlIDogZmFsc2U7CiAgICB9CiAgICBpZiAodmFsLnNpemUoKSA8IHJocy52YWwuc2l6ZSgpKQogICAgewogICAgICAgIHJldHVybiBwb3MgPyBmYWxzZSA6IHRydWU7CiAgICB9CiAgICBmb3IgKGludCBpID0gKGludCkgdmFsLnNpemUoKSAtIDE7IGkgPj0gMDsgLS1pKQogICAgewogICAgICAgIGlmICh2YWxbaV0gPCByaHMudmFsW2ldKQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIHBvcyA/IGZhbHNlIDogdHJ1ZTsKICAgICAgICB9CiAgICAgICAgaWYgKHZhbFtpXSA+IHJocy52YWxbaV0pCiAgICAgICAgewogICAgICAgICAgICByZXR1cm4gcG9zID8gdHJ1ZSA6IGZhbHNlOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBmYWxzZTsKfQoKaW5saW5lIGJvb2wgSW5mSW50OjpvcGVyYXRvcj49KGNvbnN0IEluZkludCYgcmhzKSBjb25zdAp7Ly9QUk9GSUxFRF9TQ09QRQogICAgaWYgKHBvcyAmJiAhcmhzLnBvcykKICAgIHsKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIH0KICAgIGlmICghcG9zICYmIHJocy5wb3MpCiAgICB7CiAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgfQogICAgaWYgKHZhbC5zaXplKCkgPiByaHMudmFsLnNpemUoKSkKICAgIHsKICAgICAgICByZXR1cm4gcG9zID8gdHJ1ZSA6IGZhbHNlOwogICAgfQogICAgaWYgKHZhbC5zaXplKCkgPCByaHMudmFsLnNpemUoKSkKICAgIHsKICAgICAgICByZXR1cm4gcG9zID8gZmFsc2UgOiB0cnVlOwogICAgfQogICAgZm9yIChpbnQgaSA9IChpbnQpIHZhbC5zaXplKCkgLSAxOyBpID49IDA7IC0taSkKICAgIHsKICAgICAgICBpZiAodmFsW2ldIDwgcmhzLnZhbFtpXSkKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiBwb3MgPyBmYWxzZSA6IHRydWU7CiAgICAgICAgfQogICAgICAgIGlmICh2YWxbaV0gPiByaHMudmFsW2ldKQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIHBvcyA/IHRydWUgOiBmYWxzZTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gdHJ1ZTsKfQoKaW5saW5lIHZvaWQgSW5mSW50OjpvcHRpbWl6ZVNxcnRTZWFyY2hCb3VuZHMoSW5mSW50JiBsbywgSW5mSW50JiBoaSkgY29uc3QKey8vUFJPRklMRURfU0NPUEUKICAgIEluZkludCBoZG4gPSBvbmU7CiAgICBmb3IgKGludCBpID0gKGludCkgdGhpcy0+bnVtYmVyT2ZEaWdpdHMoKSAvIDI7IGkgPj0gMjsgLS1pKQogICAgewogICAgICAgIGhkbiAqPSAxMDsKICAgIH0KICAgIGlmIChsbyA8IGhkbikKICAgIHsKICAgICAgICBsbyA9IGhkbjsKICAgIH0KICAgIGhkbiAqPSAxMDA7CiAgICBpZiAoaGkgPiBoZG4pCiAgICB7CiAgICAgICAgaGkgPSBoZG47CiAgICB9Cn0KCmlubGluZSBJbmZJbnQgSW5mSW50OjppbnRTcXJ0KCkgY29uc3QKey8vUFJPRklMRURfU0NPUEUKICAgIGlmICgqdGhpcyA8PSB6ZXJvKQogICAgewogICAgICAgIHN0ZDo6Y2VyciA8PCAiaW50U3FydCBjYWxsZWQgZm9yIG5vbi1wb3NpdGl2ZSBpbnRlZ2VyOiAiIDw8ICp0aGlzIDw8IHN0ZDo6ZW5kbDsKICAgICAgICByZXR1cm4gemVybzsKICAgIH0KICAgIEluZkludCBoaSA9ICp0aGlzIC8gdHdvICsgb25lLCBsbyA9IHplcm8sIG1pZCwgbWlkMjsKICAgIG9wdGltaXplU3FydFNlYXJjaEJvdW5kcyhsbywgaGkpOwogICAgZG8KICAgIHsKICAgICAgICBtaWQgPSAoaGkgKyBsbykgLyB0d287IC8vIDggZmFjdG9yCiAgICAgICAgbWlkMiA9IG1pZCAqIG1pZDsgLy8gMSBmYWN0b3IKICAgICAgICBpZiAobWlkMiA9PSAqdGhpcykKICAgICAgICB7CiAgICAgICAgICAgIGxvID0gbWlkOwogICAgICAgICAgICBicmVhazsKICAgICAgICB9CiAgICAgICAgZWxzZSBpZiAobWlkMiA8ICp0aGlzKQogICAgICAgIHsKICAgICAgICAgICAgbG8gPSBtaWQ7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGhpID0gbWlkOwogICAgICAgIH0KICAgIH0gd2hpbGUgKGxvIDwgaGkgLSBvbmUgJiYgbWlkMiAhPSAqdGhpcyk7CiAgICByZXR1cm4gbG87Cn0KCmlubGluZSBjaGFyIEluZkludDo6ZGlnaXRBdChzaXplX3QgaSkgY29uc3QKey8vUFJPRklMRURfU0NPUEUKICAgIGlmIChudW1iZXJPZkRpZ2l0cygpIDw9IGkpCiAgICB7CiAgICAgICAgc3RkOjpjZXJyIDw8ICJJbnZhbGlkIGRpZ2l0IGluZGV4OiAiIDw8IGkgPDwgc3RkOjplbmRsOwogICAgICAgIHJldHVybiAtMTsKICAgIH0KICAgIHJldHVybiAodmFsW2kgLyBESUdJVF9DT1VOVF0gLyBwb3dlcnNPZlRlbltpICUgRElHSVRfQ09VTlRdKSAlIDEwOwp9CgppbmxpbmUgc2l6ZV90IEluZkludDo6bnVtYmVyT2ZEaWdpdHMoKSBjb25zdAp7Ly9QUk9GSUxFRF9TQ09QRQogICAgcmV0dXJuICh2YWwuc2l6ZSgpIC0gMSkgKiBESUdJVF9DT1VOVAogICAgKyAodmFsLmJhY2soKSA+IDk5OTk5OTk5ID8gOSA6ICh2YWwuYmFjaygpID4gOTk5OTk5OSA/IDggOiAodmFsLmJhY2soKSA+IDk5OTk5OSA/IDcgOiAodmFsLmJhY2soKSA+IDk5OTk5ID8gNiA6CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAodmFsLmJhY2soKSA+IDk5OTkgPyA1IDogKHZhbC5iYWNrKCkgPiA5OTkgPyA0IDogKHZhbC5iYWNrKCkgPiA5OSA/IDMgOiAodmFsLmJhY2soKSA+IDkgPyAyIDogMSkpKSkpKSkpOwp9CgppbmxpbmUgc3RkOjpzdHJpbmcgSW5mSW50Ojp0b1N0cmluZygpIGNvbnN0CnsvL1BST0ZJTEVEX1NDT1BFCiAgICBzdGQ6Om9zdHJpbmdzdHJlYW0gb3NzOwogICAgb3NzIDw8ICp0aGlzOwogICAgcmV0dXJuIG9zcy5zdHIoKTsKfQoKaW5saW5lIHNpemVfdCBJbmZJbnQ6OnNpemUoKSBjb25zdAp7Ly9QUk9GSUxFRF9TQ09QRQogICAgcmV0dXJuIHZhbC5zaXplKCkgKiBzaXplb2YoRUxFTV9UWVBFKSArIHNpemVvZihib29sKTsKfQoKaW5saW5lIGludCBJbmZJbnQ6OnRvSW50KCkgY29uc3QKey8vUFJPRklMRURfU0NPUEUKICAgIGlmICgqdGhpcyA+IElOVF9NQVggfHwgKnRoaXMgPCBJTlRfTUlOKQogICAgc3RkOjpjZXJyIDw8ICJPdXQgb2YgSU5UIGJvdW5kczogIiA8PCAqdGhpcyA8PCBzdGQ6OmVuZGw7CiAgICBpbnQgcmVzdWx0ID0gMDsKICAgIGZvciAoaW50IGkgPSAoaW50KSB2YWwuc2l6ZSgpIC0gMTsgaSA+PSAwOyAtLWkpCiAgICB7CiAgICAgICAgcmVzdWx0ID0gcmVzdWx0ICogQkFTRSArIHZhbFtpXTsKICAgIH0KICAgIHJldHVybiBwb3MgPyByZXN1bHQgOiAtcmVzdWx0Owp9CgppbmxpbmUgbG9uZyBJbmZJbnQ6OnRvTG9uZygpIGNvbnN0CnsvL1BST0ZJTEVEX1NDT1BFCiAgICBpZiAoKnRoaXMgPiBMT05HX01BWCB8fCAqdGhpcyA8IExPTkdfTUlOKQogICAgc3RkOjpjZXJyIDw8ICJPdXQgb2YgTE9ORyBib3VuZHM6ICIgPDwgKnRoaXMgPDwgc3RkOjplbmRsOwogICAgbG9uZyByZXN1bHQgPSAwOwogICAgZm9yIChpbnQgaSA9IChpbnQpIHZhbC5zaXplKCkgLSAxOyBpID49IDA7IC0taSkKICAgIHsKICAgICAgICByZXN1bHQgPSByZXN1bHQgKiBCQVNFICsgdmFsW2ldOwogICAgfQogICAgcmV0dXJuIHBvcyA/IHJlc3VsdCA6IC1yZXN1bHQ7Cn0KCmlubGluZSBsb25nIGxvbmcgSW5mSW50Ojp0b0xvbmdMb25nKCkgY29uc3QKey8vUFJPRklMRURfU0NPUEUKICAgIGlmICgqdGhpcyA+IExPTkdfTE9OR19NQVggfHwgKnRoaXMgPCBMT05HX0xPTkdfTUlOKQogICAgc3RkOjpjZXJyIDw8ICJPdXQgb2YgTExPTkcgYm91bmRzOiAiIDw8ICp0aGlzIDw8IHN0ZDo6ZW5kbDsKICAgIGxvbmcgbG9uZyByZXN1bHQgPSAwOwogICAgZm9yIChpbnQgaSA9IChpbnQpIHZhbC5zaXplKCkgLSAxOyBpID49IDA7IC0taSkKICAgIHsKICAgICAgICByZXN1bHQgPSByZXN1bHQgKiBCQVNFICsgdmFsW2ldOwogICAgfQogICAgcmV0dXJuIHBvcyA/IHJlc3VsdCA6IC1yZXN1bHQ7Cn0KCmlubGluZSB1bnNpZ25lZCBpbnQgSW5mSW50Ojp0b1Vuc2lnbmVkSW50KCkgY29uc3QKey8vUFJPRklMRURfU0NPUEUKICAgIGlmICghcG9zIHx8ICp0aGlzID4gVUlOVF9NQVgpCiAgICBzdGQ6OmNlcnIgPDwgIk91dCBvZiBVSU5UIGJvdW5kczogIiA8PCAqdGhpcyA8PCBzdGQ6OmVuZGw7CiAgICB1bnNpZ25lZCBpbnQgcmVzdWx0ID0gMDsKICAgIGZvciAoaW50IGkgPSAoaW50KSB2YWwuc2l6ZSgpIC0gMTsgaSA+PSAwOyAtLWkpCiAgICB7CiAgICAgICAgcmVzdWx0ID0gcmVzdWx0ICogQkFTRSArIHZhbFtpXTsKICAgIH0KICAgIHJldHVybiByZXN1bHQ7Cn0KCmlubGluZSB1bnNpZ25lZCBsb25nIEluZkludDo6dG9VbnNpZ25lZExvbmcoKSBjb25zdAp7Ly9QUk9GSUxFRF9TQ09QRQogICAgaWYgKCFwb3MgfHwgKnRoaXMgPiBVTE9OR19NQVgpCiAgICBzdGQ6OmNlcnIgPDwgIk91dCBvZiBVTE9ORyBib3VuZHM6ICIgPDwgKnRoaXMgPDwgc3RkOjplbmRsOwogICAgdW5zaWduZWQgbG9uZyByZXN1bHQgPSAwOwogICAgZm9yIChpbnQgaSA9IChpbnQpIHZhbC5zaXplKCkgLSAxOyBpID49IDA7IC0taSkKICAgIHsKICAgICAgICByZXN1bHQgPSByZXN1bHQgKiBCQVNFICsgdmFsW2ldOwogICAgfQogICAgcmV0dXJuIHJlc3VsdDsKfQoKaW5saW5lIHVuc2lnbmVkIGxvbmcgbG9uZyBJbmZJbnQ6OnRvVW5zaWduZWRMb25nTG9uZygpIGNvbnN0CnsvL1BST0ZJTEVEX1NDT1BFCiAgICBpZiAoIXBvcyB8fCAqdGhpcyA+IFVMT05HX0xPTkdfTUFYKQogICAgc3RkOjpjZXJyIDw8ICJPdXQgb2YgVUxMT05HIGJvdW5kczogIiA8PCAqdGhpcyA8PCBzdGQ6OmVuZGw7CiAgICB1bnNpZ25lZCBsb25nIGxvbmcgcmVzdWx0ID0gMDsKICAgIGZvciAoaW50IGkgPSAoaW50KSB2YWwuc2l6ZSgpIC0gMTsgaSA+PSAwOyAtLWkpCiAgICB7CiAgICAgICAgcmVzdWx0ID0gcmVzdWx0ICogQkFTRSArIHZhbFtpXTsKICAgIH0KICAgIHJldHVybiByZXN1bHQ7Cn0KCmlubGluZSB2b2lkIEluZkludDo6dHJ1bmNhdGVUb0Jhc2UoKQp7Ly9QUk9GSUxFRF9TQ09QRQogICAgZm9yIChzaXplX3QgaSA9IDA7IGkgPCB2YWwuc2l6ZSgpOyArK2kpIC8vIHRydW5jYXRlIGVhY2gKICAgIHsKICAgICAgICBpZiAodmFsW2ldID49IEJBU0UgfHwgdmFsW2ldIDw9IC1CQVNFKQogICAgICAgIHsvL1BST0ZJTEVEX1NDT1BFCiAgICAgICAgICAgIGRpdl90IGR0ID0gZGl2KHZhbFtpXSwgQkFTRSk7CiAgICAgICAgICAgIHZhbFtpXSA9IGR0LnJlbTsKICAgICAgICAgICAgaWYgKGkgKyAxID49IHZhbC5zaXplKCkpCiAgICAgICAgICAgIHsvL1BST0ZJTEVEX1NDT1BFCiAgICAgICAgICAgICAgICB2YWwucHVzaF9iYWNrKGR0LnF1b3QpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgey8vUFJPRklMRURfU0NPUEUKICAgICAgICAgICAgICAgIHZhbFtpICsgMV0gKz0gZHQucXVvdDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQoKaW5saW5lIGJvb2wgSW5mSW50OjplcXVhbGl6ZVNpZ25zKCkKey8vUFJPRklMRURfU0NPUEUKICAgIGJvb2wgaXNQb3NpdGl2ZSA9IHRydWU7CiAgICBpbnQgaSA9IChpbnQpICgodmFsLnNpemUoKSkpIC0gMTsKICAgIGZvciAoOyBpID49IDA7IC0taSkKICAgIHsKICAgICAgICBpZiAodmFsW2ldICE9IDApCiAgICAgICAgewogICAgICAgICAgICBpc1Bvc2l0aXZlID0gdmFsW2ktLV0gPiAwOwogICAgICAgICAgICBicmVhazsKICAgICAgICB9CiAgICB9CgogICAgaWYgKGlzUG9zaXRpdmUpCiAgICB7CiAgICAgICAgZm9yICg7IGkgPj0gMDsgLS1pKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKHZhbFtpXSA8IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGludCBrID0gMCwgaW5kZXggPSBpICsgMTsKICAgICAgICAgICAgICAgIGZvciAoOyAoc2l6ZV90KShpbmRleCkgPCB2YWwuc2l6ZSgpICYmIHZhbFtpbmRleF0gPT0gMDsgKytrLCArK2luZGV4KTsgLy8gY291bnQgYWRqYWNlbnQgemVyb3Mgb24gbGVmdAogICAgICAgICAgICAgICAgLy9pZiAoKHNpemVfdCkoaW5kZXgpIDwgdmFsLnNpemUoKSAmJiB2YWxbaW5kZXhdID4gMCkKICAgICAgICAgICAgICAgIHsgLy8gbnVtYmVyIG9uIHRoZSBsZWZ0IGlzIHBvc2l0aXZlCiAgICAgICAgICAgICAgICAgICAgdmFsW2luZGV4XSAtPSAxOwogICAgICAgICAgICAgICAgICAgIHZhbFtpXSArPSBCQVNFOwogICAgICAgICAgICAgICAgICAgIGZvciAoOyBrID4gMDsgLS1rKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgdmFsW2kgKyBrXSA9IFVQUEVSX0JPVU5EOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgICBmb3IgKDsgaSA+PSAwOyAtLWkpCiAgICAgICAgewogICAgICAgICAgICBpZiAodmFsW2ldID4gMCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IGsgPSAwLCBpbmRleCA9IGkgKyAxOwogICAgICAgICAgICAgICAgZm9yICg7IChzaXplX3QpKGluZGV4KSA8IHZhbC5zaXplKCkgJiYgdmFsW2luZGV4XSA9PSAwOyArK2ssICsraW5kZXgpOyAvLyBjb3VudCBhZGphY2VudCB6ZXJvcyBvbiByaWdodAogICAgICAgICAgICAgICAgLy9pZiAoKHNpemVfdCkoaW5kZXgpIDwgdmFsLnNpemUoKSAmJiB2YWxbaW5kZXhdIDwgMCkKICAgICAgICAgICAgICAgIHsgLy8gbnVtYmVyIG9uIHRoZSBsZWZ0IGlzIG5lZ2F0aXZlCiAgICAgICAgICAgICAgICAgICAgdmFsW2luZGV4XSArPSAxOwogICAgICAgICAgICAgICAgICAgIHZhbFtpXSAtPSBCQVNFOwogICAgICAgICAgICAgICAgICAgIGZvciAoOyBrID4gMDsgLS1rKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgdmFsW2kgKyBrXSA9IC1VUFBFUl9CT1VORDsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICAKICAgIHJldHVybiBpc1Bvc2l0aXZlOwp9CgppbmxpbmUgdm9pZCBJbmZJbnQ6OnJlbW92ZUxlYWRpbmdaZXJvcygpCnsvL1BST0ZJTEVEX1NDT1BFCiAgICBmb3IgKGludCBpID0gKGludCkgKHZhbC5zaXplKCkpIC0gMTsgaSA+IDA7IC0taSkgLy8gcmVtb3ZlIGxlYWRpbmcgMCdzCiAgICB7CiAgICAgICAgaWYgKHZhbFtpXSAhPSAwKQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICB2YWwuZXJhc2UodmFsLmJlZ2luKCkgKyBpKTsKICAgICAgICB9CiAgICB9Cn0KCmlubGluZSB2b2lkIEluZkludDo6Y29ycmVjdChib29sIGp1c3RDaGVja0xlYWRpbmdaZXJvcywgYm9vbCBoYXNWYWxpZFNpZ24pCnsvL1BST0ZJTEVEX1NDT1BFCiAgICBpZiAoIWp1c3RDaGVja0xlYWRpbmdaZXJvcykKICAgIHsKICAgICAgICB0cnVuY2F0ZVRvQmFzZSgpOwogICAgICAgIAogICAgICAgIGlmIChlcXVhbGl6ZVNpZ25zKCkpCiAgICAgICAgewogICAgICAgICAgICBwb3MgPSAoKHZhbC5zaXplKCkgPT0gMSAmJiB2YWxbMF0gPT0gMCkgfHwgIWhhc1ZhbGlkU2lnbikgPyB0cnVlIDogcG9zOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBwb3MgPSBoYXNWYWxpZFNpZ24gPyAhcG9zIDogZmFsc2U7CiAgICAgICAgICAgIGZvciAoc2l6ZV90IGkgPSAwOyBpIDwgdmFsLnNpemUoKTsgKytpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB2YWxbaV0gPSBhYnModmFsW2ldKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIAogICAgcmVtb3ZlTGVhZGluZ1plcm9zKCk7Cn0KCmlubGluZSB2b2lkIEluZkludDo6ZnJvbVN0cmluZyhjb25zdCBzdGQ6OnN0cmluZyYgcykKey8vUFJPRklMRURfU0NPUEUKICAgIHBvcyA9IHRydWU7CiAgICB2YWwuY2xlYXIoKTsKICAgIC8vIFRPRE8gdXNlIHJlc2l6ZQogICAgdmFsLnJlc2VydmUocy5zaXplKCkgLyBESUdJVF9DT1VOVCArIDEpOwogICAgaW50IGkgPSAoaW50KSBzLnNpemUoKSAtIERJR0lUX0NPVU5UOwogICAgZm9yICg7IGkgPj0gMDsgaSAtPSBESUdJVF9DT1VOVCkKICAgIHsKICAgICAgICB2YWwucHVzaF9iYWNrKGF0b2kocy5zdWJzdHIoaSwgRElHSVRfQ09VTlQpLmNfc3RyKCkpKTsKICAgIH0KICAgIGlmIChpID4gLURJR0lUX0NPVU5UKQogICAgewogICAgICAgIHN0ZDo6c3RyaW5nIHNzID0gcy5zdWJzdHIoMCwgaSArIERJR0lUX0NPVU5UKTsKICAgICAgICBpZiAoc3Muc2l6ZSgpID09IDEgJiYgc3NbMF0gPT0gJy0nKQogICAgICAgIHsKICAgICAgICAgICAgcG9zID0gZmFsc2U7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIHZhbC5wdXNoX2JhY2soYXRvaShzcy5jX3N0cigpKSk7CiAgICAgICAgfQogICAgfQogICAgaWYgKHZhbC5iYWNrKCkgPCAwKQogICAgewogICAgICAgIHZhbC5iYWNrKCkgPSAtdmFsLmJhY2soKTsKICAgICAgICBwb3MgPSBmYWxzZTsKICAgIH0KICAgIGNvcnJlY3QodHJ1ZSk7Cn0KCmlubGluZSBFTEVNX1RZUEUgSW5mSW50OjpkSW5SKGNvbnN0IEluZkludCYgUiwgY29uc3QgSW5mSW50JiBEKQp7Ly9QUk9GSUxFRF9TQ09QRQogICAgRUxFTV9UWVBFIG1pbiA9IDAsIG1heCA9IFVQUEVSX0JPVU5EOwogICAgd2hpbGUgKG1heCAtIG1pbiA+IDApCiAgICB7CiAgICAgICAgRUxFTV9UWVBFIGF2ZyA9IG1heCArIG1pbjsKICAgICAgICAvL2Rpdl90IGR0ID0gZGl2KGF2ZywgMik7CiAgICAgICAgLy9hdmcgPSBkdC5yZW0gPyAoZHQucXVvdCArIDEpIDogZHQucXVvdDsKICAgICAgICBFTEVNX1RZUEUgaGF2ZyA9IGF2ZyAvIDI7CiAgICAgICAgYXZnID0gKGF2ZyAtIGhhdmcgKiAyKSA/IChoYXZnICsgMSkgOiBoYXZnOwogICAgICAgIEluZkludCBwcm9kID0gRCAqIGF2ZzsKICAgICAgICBpZiAoUiA9PSBwcm9kKQogICAgICAgIHsvL1BST0ZJTEVEX1NDT1BFCiAgICAgICAgICAgIHJldHVybiBhdmc7CiAgICAgICAgfQogICAgICAgIGVsc2UgaWYgKFIgPiBwcm9kKQogICAgICAgIHsvL1BST0ZJTEVEX1NDT1BFCiAgICAgICAgICAgIG1pbiA9IGF2ZzsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsvL1BST0ZJTEVEX1NDT1BFCiAgICAgICAgICAgIG1heCA9IGF2ZyAtIDE7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIG1pbjsKfQoKaW5saW5lIHZvaWQgSW5mSW50OjptdWx0aXBseUJ5RGlnaXQoRUxFTV9UWVBFIGZhY3Rvciwgc3RkOjp2ZWN0b3I8RUxFTV9UWVBFPiYgdmFsKQp7Ly9QUk9GSUxFRF9TQ09QRQogICAgRUxFTV9UWVBFIGNhcnJ5ID0gMDsKICAgIGZvciAoc2l6ZV90IGkgPSAwOyBpIDwgdmFsLnNpemUoKTsgKytpKQogICAgewogICAgICAgIFBST0RVQ1RfVFlQRSBwdmFsID0gdmFsW2ldICogKFBST0RVQ1RfVFlQRSkgZmFjdG9yICsgY2Fycnk7CiAgICAgICAgaWYgKHB2YWwgPj0gQkFTRSB8fCBwdmFsIDw9IC1CQVNFKQogICAgICAgIHsKICAgICAgICAgICAgLy9jYXJyeSA9IChFTEVNX1RZUEUpIChwdmFsIC8gQkFTRSk7CiAgICAgICAgICAgIC8vcHZhbCAlPSBCQVNFOwoKICAgICAgICAgICAgY2FycnkgPSAoRUxFTV9UWVBFKSAocHZhbCAvIEJBU0UpOwogICAgICAgICAgICBwdmFsIC09IGNhcnJ5ICogQkFTRTsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgY2FycnkgPSAwOwogICAgICAgIH0KICAgICAgICB2YWxbaV0gPSAoRUxFTV9UWVBFKSBwdmFsOwogICAgfQogICAgaWYgKGNhcnJ5ID4gMCkKICAgIHsKICAgICAgICB2YWwucHVzaF9iYWNrKGNhcnJ5KTsKICAgIH0KfQoKLyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqLwovKioqKioqKioqKioqKioqKioqKiogTk9OLU1FTUJFUiBPUEVSQVRPUlMgKioqKioqKioqKioqKioqKioqKiovCi8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKi8KCmlubGluZSBzdGQ6OmlzdHJlYW0mIG9wZXJhdG9yPj4oc3RkOjppc3RyZWFtICZzLCBJbmZJbnQgJm4pCnsvL1BST0ZJTEVEX1NDT1BFCiAgICBzdGQ6OnN0cmluZyBzdHI7CiAgICBzID4+IHN0cjsKICAgIG4uZnJvbVN0cmluZyhzdHIpOwogICAgcmV0dXJuIHM7Cn0KCmlubGluZSBzdGQ6Om9zdHJlYW0mIG9wZXJhdG9yPDwoc3RkOjpvc3RyZWFtICZzLCBjb25zdCBJbmZJbnQgJm4pCnsvL1BST0ZJTEVEX1NDT1BFCiAgICBpZiAoIW4ucG9zKQogICAgewogICAgICAgIHMgPDwgJy0nOwogICAgfQogICAgYm9vbCBmaXJzdCA9IHRydWU7CiAgICBmb3IgKGludCBpID0gKGludCkgbi52YWwuc2l6ZSgpIC0gMTsgaSA+PSAwOyAtLWkpCiAgICB7CiAgICAgICAgaWYgKGZpcnN0KQogICAgICAgIHsKICAgICAgICAgICAgcyA8PCBuLnZhbFtpXTsKICAgICAgICAgICAgZmlyc3QgPSBmYWxzZTsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgcyA8PCBzdGQ6OnNldGZpbGwoJzAnKSA8PCBzdGQ6OnNldHcoRElHSVRfQ09VTlQpIDw8IG4udmFsW2ldOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBzOwp9Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgbWFpbigpewogICAgaW50IGE7CiAgICBjaW4gPj4gYTsKICAgIEluZkludCB4ID0gMSwga2c7CiAgICBmb3IgKGludCBjb250ID0gMDsgY29udCA8IGE7IGNvbnQrKykgewogICAgICAgIHggKj0gMjsKICAgIH0KICAgIGtnID0geCAvIDEyMDAwOwogICAgY291dCA8PCBrZyA8PCAiIGtnXG4iOwp9Cg==

Success #stdin #stdout 0s 3476KB

stdin

copy

stdout

copy

1537228672809129 kg

https://ideone.com/3WEEFC

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language