#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

using namespace std;

static_assert(sizeof(long) == 8, "long must be 64-bit.");

// ****************************************************************************
// BEGIN INT IMPLEMENTATION

template <typename T, typename Return = void>
using EnsureIntegral = enable_if_t<is_integral<T>::value, Return>;

class Int final {
public:
using Limb = uint64_t;
enum class Sign : bool { POS, NEG };

Int() noexcept: limbs_(), sign_(Sign::POS) {}
explicit Int(int64_t value): limbs_(),
 sign_(value >= 0 ? Sign::POS : Sign::NEG) {
if (value == 0)
return;
if (value == -0x7FFFFFFFFFFFFFFE - 1) {
limbs_.push_back(0x7FFFFFFFFFFFFFFF);
return;
}
uint64_t unsignedValue =
static_cast<uint64_t>(sign_ == Sign::POS ? value : -value);
limbs_.push_back(unsignedValue);
}
explicit Int(uint64_t value): limbs_(), sign_(Sign::POS) {
if (value != 0)
limbs_.push_back(value);
}
template <typename I, typename = EnsureIntegral<I>>
explicit Int(I value) : Int(
static_cast<conditional_t<is_signed<I>::value, int64_t, uint64_t>>(
value)) {}
explicit Int(const char* value): Int(value, strlen(value)) {}
explicit Int(const char* str, size_t size): limbs_(), sign_(Sign::POS) {
assert(size > 0);
Sign sign = Sign::POS;
if (*str == '+') {
++str;
--size;
} else if (*str == '-') {
sign = Sign::NEG;
++str;
--size;
}
assert(size > 0);
static constexpr size_t UNIT_SIZE = 19;
static constexpr Limb UNIT = 10000000000000000000u;
size_t units = size / UNIT_SIZE;
size_t remainder = size % UNIT_SIZE;
if (remainder > 0) {
Limb value = parseLimb(str, str + remainder);
*this += value;
str += remainder;
size -= remainder;
}
for (; units > 0; --units) {
*this *= UNIT;
Limb value = parseLimb(str, str + UNIT_SIZE);
*this += value;
str += UNIT_SIZE;
size -= UNIT_SIZE;
}
if (!limbs_.empty())
sign_ = sign;
}
explicit Int(const string& str): Int(str.data(), str.size()) {}

Int(const Int& other): limbs_(other.limbs_), sign_(other.sign_) {}
Int& operator=(const Int& other) {
limbs_ = other.limbs_;
sign_ = other.sign_;
return *this;
}
Int(Int&& other) noexcept: limbs_(move(other.limbs_)), sign_(other.sign_) {
other.limbs_.clear();
other.sign_ = Sign::POS;
}
Int& operator=(Int&& other) noexcept {
limbs_ = move(other.limbs_);
sign_ = other.sign_;
other.limbs_.clear();
other.sign_ = Sign::POS;
return *this;
}
~Int() noexcept {}

template <typename I, typename = EnsureIntegral<I>>
explicit operator I() const {
if (limbs_.empty())
return 0;
Limb value = limbs_.front();
if (is_signed<I>::value &&
sign_ == Sign::NEG &&
static_cast<Limb>(numeric_limits<I>::max()) + 1 == value) {
return numeric_limits<I>::min();
}
if (sign_ == Sign::NEG) {
return static_cast<I>(-static_cast<make_signed_t<Limb>>(value));
}
return static_cast<I>(value);
}

bool operator==(const Int& other) const {
return sign_ == other.sign_ && limbs_ == other.limbs_;
}
bool operator!=(const Int& other) const { return !(*this == other); }
bool operator<(const Int& other) const {
switch (sign_) {
case Sign::POS:
switch (other.sign_) {
case Sign::POS:
return compareImpl(
limbs_.data(), limbs_.size(),
other.limbs_.data(), other.limbs_.size()) < 0;
case Sign::NEG:
return false;
}
break;
case Sign::NEG:
switch (other.sign_) {
case Sign::POS:
return true;
case Sign::NEG:
return compareImpl(
limbs_.data(), limbs_.size(),
other.limbs_.data(), other.limbs_.size()) > 0;
}
break;
}
assert(false);
return false;
}
bool operator>(const Int& other) const { return other < *this; }
bool operator<=(const Int& other) const { return !(*this > other); }
bool operator>=(const Int& other) const { return !(*this < other); }

Int operator+() const { return *this; }
Int& negate() & {
if (!limbs_.empty())
sign_ = reverseSign(sign_);
return *this;
}
Int negate() && { negate(); return move(*this); }
Int operator-() const {
Int result(*this);
result.negate();
return result;
}
bool operator!() const { return limbs_.empty(); }
explicit operator bool() const { return !limbs_.empty(); }

Int& operator++() & {
switch (sign_) {
case Sign::POS: {
bool carry = incrementImpl(limbs_.data(), limbs_.size());
if (carry)
limbs_.push_back(1);
break;
}
case Sign::NEG: {
bool borrow = decrementImpl(limbs_.data(), limbs_.size());
assert(!borrow);
if (limbs_.back() == 0)
limbs_.pop_back();
if (limbs_.empty())
sign_ = Sign::POS;
break;
}
}
return *this;
}
Int operator++() && { operator++(); return move(*this); }
Int operator++(int) {
Int result(*this);
++(*this);
return result;
}
Int& operator--() & {
switch (sign_) {
case Sign::POS: {
bool borrow = decrementImpl(limbs_.data(), limbs_.size());
if (borrow) {
assert(limbs_.empty());
sign_ = Sign::NEG;
limbs_.push_back(1);
} else if (limbs_.back() == 0) {
limbs_.pop_back();
}
break;
}
case Sign::NEG: {
bool carry = incrementImpl(limbs_.data(), limbs_.size());
if (carry)
limbs_.push_back(1);
break;
}
}
return *this;
}
Int operator--() && { operator--(); return move(*this); }
Int operator--(int) {
Int result(*this);
--(*this);
return result;
}
Int& operator+=(const Int& addend) & {
if (sign_ == addend.sign_) {
if (limbs_.size() < addend.limbs_.size())
limbs_.resize(addend.limbs_.size());
size_t size = addend.limbs_.size();
bool carry = addImpl(limbs_.data(), addend.limbs_.data(), size);
if (carry) {
carry = incrementImpl(limbs_.data() + size,
limbs_.size() - size);
if (carry)
limbs_.push_back(1);
}
} else {
if (limbs_.size() < addend.limbs_.size())
limbs_.resize(addend.limbs_.size());
size_t size = addend.limbs_.size();
bool borrow;
if (compareImpl(limbs_.data(), limbs_.size(),
addend.limbs_.data(), addend.limbs_.size()) < 0) {
borrow = subtractReversedImpl(
addend.limbs_.data(), limbs_.data(), size);
sign_ = reverseSign(sign_);
} else {
borrow = subtractImpl(limbs_.data(),
addend.limbs_.data(), size);
}
if (borrow) {
borrow = decrementImpl(limbs_.data() + size,
 limbs_.size() - size);
assert(!borrow);
}
while (!limbs_.empty() && limbs_.back() == 0)
limbs_.pop_back();
if (limbs_.empty())
sign_ = Sign::POS;
}
return *this;
}
Int& operator-=(const Int& subtrahend) & {
if (sign_ != subtrahend.sign_) {
if (limbs_.size() < subtrahend.limbs_.size())
limbs_.resize(subtrahend.limbs_.size());
size_t size = subtrahend.limbs_.size();
bool carry = addImpl(limbs_.data(), subtrahend.limbs_.data(), size);
if (carry) {
carry = incrementImpl(limbs_.data() + size,
limbs_.size() - size);
if (carry)
limbs_.push_back(1);
}
} else {
if (limbs_.size() < subtrahend.limbs_.size())
limbs_.resize(subtrahend.limbs_.size());
size_t size = subtrahend.limbs_.size();
bool borrow;
if (compareImpl(
limbs_.data(), limbs_.size(),
subtrahend.limbs_.data(), subtrahend.limbs_.size()) < 0) {
borrow = subtractReversedImpl(
subtrahend.limbs_.data(), limbs_.data(), size);
sign_ = reverseSign(sign_);
} else {
borrow = subtractImpl(limbs_.data(), subtrahend.limbs_.data(),
size);
}
if (borrow) {
borrow = decrementImpl(limbs_.data() + size,
 limbs_.size() - size);
assert(!borrow);
}
while (!limbs_.empty() && limbs_.back() == 0)
limbs_.pop_back();
if (limbs_.empty())
sign_ = Sign::POS;
}
return *this;
}
Int& operator*=(const Int& multiplier) & {
if (limbs_.empty() || multiplier.limbs_.empty()) {
limbs_.clear();
sign_ = Sign::POS;
} else {
size_t size = limbs_.size() + multiplier.limbs_.size();
vector<Limb> result(size, 0);
multiplyImpl(limbs_.data(), limbs_.size(),
 multiplier.limbs_.data(), multiplier.limbs_.size(),
 result.data());
while (result.back() == 0)
result.pop_back();
sign_ = sign_ == multiplier.sign_ ? Sign::POS : Sign::NEG;
limbs_ = move(result);
}
return *this;
}
Int& operator/=(const Int& divisor) & {
assert(!divisor.limbs_.empty());
size_t dividendSize = limbs_.size();
size_t divisorSize = divisor.limbs_.size();
vector<Limb> quotient(
dividendSize < divisorSize - 1 ? 0 :
dividendSize + 1 - divisorSize);
vector<Limb> remainder(divisorSize);

divideImpl(limbs_.data(), dividendSize, divisor.limbs_.data(),
 divisorSize, quotient.data(), remainder.data());
sign_ = sign_ == divisor.sign_ ? Sign::POS : Sign::NEG;
limbs_ = move(quotient);
while (!limbs_.empty() && limbs_.back() == 0)
limbs_.pop_back();
if (limbs_.empty())
sign_ = Sign::POS;
return *this;
}
Int& operator%=(const Int& divisor) & {
assert(!divisor.limbs_.empty());
size_t dividendSize = limbs_.size();
size_t divisorSize = divisor.limbs_.size();
vector<Limb> quotient(
dividendSize < divisorSize - 1 ? 0 :
dividendSize + 1 - divisorSize);
vector<Limb> remainder(divisorSize);
divideImpl(limbs_.data(), dividendSize, divisor.limbs_.data(),
 divisorSize, quotient.data(), remainder.data());
Sign dividendSign = sign_;
sign_ = Sign::POS;
limbs_ = move(remainder);
while (!limbs_.empty() && limbs_.back() == 0)
limbs_.pop_back();
if (dividendSign == Sign::NEG && !limbs_.empty())
sign_ = Sign::NEG;
return *this;
}
Int operator+=(const Int& addend) && {
operator+=(addend); return move(*this);
}
Int operator-=(const Int& subtrahend) && {
operator-=(subtrahend); return move(*this);
}
Int operator*=(const Int& multiplier) && {
operator*=(multiplier); return move(*this);
}
Int operator/=(const Int& divisor) && {
operator/=(divisor); return move(*this);
}
Int operator%=(const Int& divisor) && {
operator%=(divisor); return move(*this);
}
Int operator+(const Int& addend) const {
return Int(*this) += addend;
}
Int operator-(const Int& subtrahend) const {
return Int(*this) -= subtrahend;
}
Int operator*(const Int& multiplier) const {
return Int(*this) *= multiplier;
}
Int operator/(const Int& divisor) const {
return Int(*this) /= divisor;
}
Int operator%(const Int& divisor) const {
return Int(*this) %= divisor;
}
tuple<Int, Int> divMod(const Int& divisor) const {
assert(!divisor.limbs_.empty());
size_t dividendSize = limbs_.size();
size_t divisorSize = divisor.limbs_.size();
vector<Limb> quotientBuffer(dividendSize < divisorSize - 1 ? 0 :
dividendSize + 1 - divisorSize);
vector<Limb> remainderBuffer(divisorSize);
divideImpl(limbs_.data(), dividendSize, divisor.limbs_.data(),
 divisorSize, quotientBuffer.data(), remainderBuffer.data());
Int quotient(move(quotientBuffer),
 sign_ == divisor.sign_ ? Sign::POS : Sign::NEG);
Int remainder(move(remainderBuffer), Sign::POS);
if (sign_ == Sign::NEG && !remainder.limbs_.empty())
remainder -= divisor;
return make_tuple(move(quotient), move(remainder));
}
template <typename OStream>
OStream& serialize(OStream& out) const {
static constexpr size_t UNIT_SIZE = 19;
static constexpr Limb UNIT = 10000000000000000000u;
Int value(*this);
if (sign_ == Sign::NEG) {
out << '-';
value.negate();
}
vector<Limb> units;
while (value > Int(0)) {
Int rem;
tie(value, rem) = value.divMod(UNIT);
units.push_back(static_cast<Limb>(rem));
}
if (units.empty()) {
out << '0';
} else {
auto it = units.rbegin();
out << *it;
++it;
for (; it != units.rend(); ++it)
out << setfill('0') << setw(UNIT_SIZE) << *it;
}
return out;
}

template <typename T, typename = EnsureIntegral<T>>
Int& operator+=(T addend) & { return operator+=(Int(addend)); }
template <typename T, typename = EnsureIntegral<T>>
Int operator+=(T addend) && { operator+=(addend); return move(*this); }
template <typename T, typename = EnsureIntegral<T>>
Int& operator-=(T subtrahend) & { return operator-=(Int(subtrahend)); }
template <typename T, typename = EnsureIntegral<T>>
Int operator-=(T subtrahend) && { operator-=(subtrahend);
return move(*this); }
template <typename T, typename = EnsureIntegral<T>>
Int& operator*=(T multiplier) & { return operator*=(Int(multiplier)); }
template <typename T, typename = EnsureIntegral<T>>
Int operator*=(T multiplier) && { operator*=(multiplier);
return move(*this); }
template <typename T, typename = EnsureIntegral<T>>
Int& operator/=(T dividend) & { return operator/=(Int(dividend)); }
template <typename T, typename = EnsureIntegral<T>>
Int operator/=(T dividend) && { operator/=(dividend); return move(*this); }
template <typename T, typename = EnsureIntegral<T>>
Int& operator%=(T dividend) & { return operator%=(Int(dividend)); }
template <typename T, typename = EnsureIntegral<T>>
Int operator%=(T dividend) && { operator%=(dividend); return move(*this); }

template <typename T, typename = EnsureIntegral<T>>
tuple<Int, Int> divMod(T divisor) const { return divMod(Int(divisor)); }

private:
using DoubleLimb = unsigned __int128;
explicit Int(vector<Limb>&& limbs, Sign sign)
: limbs_(move(limbs)), sign_(sign) {
while (!limbs_.empty() && limbs_.back() == 0)
limbs_.pop_back();
if (limbs_.empty())
sign_ = Sign::POS;
}

static Limb parseLimb(const char* begin, const char* end) {
Limb r = 0;
for (const char* p = begin; p != end; ++p) {
assert(*p >= '0' && *p <= '9');
r *= 10;
r += *p - '0';
}
return r;
}
static Sign reverseSign(Sign sign) {
if (sign == Sign::POS) return Sign::NEG;
return Sign::POS;
}
static int compareImpl(const Limb* leftLimbs, size_t leftSize,
 const Limb* rightLimbs, size_t rightSize) {
if (leftSize < rightSize)
return -1;
if (leftSize > rightSize)
return 1;
size_t size = leftSize;
leftLimbs += size;
rightLimbs += size;
for (; size > 0; --size) {
--leftLimbs;
--rightLimbs;
if (*leftLimbs < *rightLimbs)
return -1;
if (*leftLimbs > *rightLimbs)
return 1;
}
return 0;
}
static bool incrementImpl(Limb* limb, size_t size) {
for (; size > 0; --size) {
++(*limb);
if (*limb != 0)
return 0;
++limb;
}
return 1;
}
static bool decrementImpl(Limb* limb, size_t size) {
for (; size > 0; --size) {
--(*limb);
if (*limb != MAX)
return 0;
++limb;
}
return 1;
}
static Limb addShort(Limb augend, Limb addend, bool& overflow) {
augend += addend;
overflow = augend < addend;
return augend;
}
static bool addImpl(Limb* augend, const Limb* addend, size_t size) {
if (size == 0)
return 0;
bool carry;
*augend = addShort(*augend, *addend, carry);
--size;
++augend;
++addend;
for (; size > 0; --size, ++augend, ++addend) {
bool carry1;
bool carry2;
*augend = addShort(*augend, *addend, carry1);
*augend = addShort(*augend, carry, carry2);
carry = carry1 || carry2;
}
return carry;
}
static Limb subtractShort(Limb minuend, Limb subtrahend, bool& overflow) {
Limb result = minuend - subtrahend;
overflow = result > minuend;
return result;
}
static bool subtractImpl(Limb* minuend, const Limb* subtrahend,
 size_t size) {
if (size == 0)
return 0;
bool borrow;
*minuend = subtractShort(*minuend, *subtrahend, borrow);
--size;
++minuend;
++subtrahend;
for (; size > 0; --size, ++minuend, ++subtrahend) {
bool borrow1;
bool borrow2;
*minuend = subtractShort(*minuend, *subtrahend, borrow1);
*minuend = subtractShort(*minuend, borrow, borrow2);
borrow = borrow1 || borrow2;
}
return borrow;
}
static bool subtractReversedImpl(const Limb* minuend, Limb* subtrahend,
 size_t size) {
if (size == 0)
return 0;
bool borrow;
*subtrahend = subtractShort(*minuend, *subtrahend, borrow);
--size;
++minuend;
++subtrahend;
for (; size > 0; --size, ++minuend, ++subtrahend) {
bool borrow1;
bool borrow2;
*subtrahend = subtractShort(*minuend, *subtrahend, borrow1);
*subtrahend = subtractShort(*subtrahend, borrow, borrow2);
borrow = borrow1 || borrow2;
}
return borrow;
}
static void multiplyShort(Limb multiplicand, Limb multiplier,
Limb& productLow, Limb& productHigh) {
DoubleLimb product =
static_cast<DoubleLimb>(multiplicand) *
static_cast<DoubleLimb>(multiplier);
productLow = static_cast<Limb>(product);
productHigh = static_cast<Limb>(product >> BITS);
}
static void multiplyImpl(const Limb* multiplicand, size_t multiplicandSize,
 const Limb* multiplier, size_t multiplierSize,
 Limb* product) {
size_t size = multiplicandSize + multiplierSize;
for (; multiplicandSize > 0;
 --multiplicandSize, ++multiplicand, ++product, --size) {
const Limb* innerMultiplier = multiplier;
Limb* innerProduct = product;
size_t innerSize = size;
for (size_t innerMultiplierSize = multiplierSize;
 innerMultiplierSize > 0;
 --innerMultiplierSize, ++innerMultiplier, ++innerProduct,
 --innerSize) {
Limb low;
Limb high;
multiplyShort(*multiplicand, *innerMultiplier, low, high);

bool carry;
innerProduct[0] = addShort(innerProduct[0], low, carry);
if (carry) {
carry = incrementImpl(innerProduct + 1, innerSize - 1);
assert(!carry);
}

innerProduct[1] = addShort(innerProduct[1], high, carry);
if (carry) {
carry = incrementImpl(innerProduct + 2, innerSize - 2);
assert(!carry);
}
}
}
}
static void divideShort(Limb dividendLow, Limb dividendHigh, Limb divisor,
Limb& quotient, Limb& remainder) {
assert(divisor != 0u);
assert(dividendHigh < divisor);
DoubleLimb dividend =
(static_cast<DoubleLimb>(dividendHigh) << BITS) |
static_cast<DoubleLimb>(dividendLow);
quotient = static_cast<Limb>(
dividend / static_cast<DoubleLimb>(divisor));
remainder = static_cast<Limb>(
dividend % static_cast<DoubleLimb>(divisor));
}
static void divideImpl(const Limb* dividend, size_t dividendSize,
 const Limb* divisor, size_t divisorSize,
 Limb* quotient, Limb* remainder) {
assert(divisorSize > 0);
assert(divisor[divisorSize - 1] > 0u);
if (compareImpl(dividend, dividendSize, divisor, divisorSize) < 0) {
assert(dividendSize <= divisorSize);
copy(dividend, dividend + dividendSize, remainder);
return;
}
assert(dividendSize >= divisorSize);
if (divisorSize == 1) {
Limb div = *divisor;
if (dividendSize == 1) {
*quotient = *dividend / div;
*remainder = *dividend % div;
return;
}
const Limb* dividendPointer = dividend + dividendSize - 1;
Limb* quotientPointer = quotient + dividendSize - 1;
Limb valueHigh = 0;
Limb valueLow = *dividendPointer;
if (valueLow < div) {
assert(dividendPointer != dividend);
--dividendPointer;
--quotientPointer;
valueHigh = valueLow;
valueLow = *dividendPointer;
}
while (true) {
divideShort(valueLow, valueHigh, div, *quotientPointer,
valueLow);
if (dividendPointer == dividend)
break;
--dividendPointer;
--quotientPointer;
valueHigh = valueLow;
valueLow = *dividendPointer;
}
*remainder = valueLow;
return;
}
const Limb* const dividendArg = dividend;
const Limb* const divisorArg = divisor;
vector<Limb> dividendBuffer;
vector<Limb> divisorBuffer;
Limb shift = countLeadingZeros(divisorArg[divisorSize - 1]);
if (shift > 0) {
dividendBuffer.resize(dividendSize + 1);
for (size_t i = 0; i < dividendSize; ++i) {
size_t index = dividendSize - 1 - i;
dividendBuffer[index + 1] |=
dividendArg[index] >> (BITS - shift);
dividendBuffer[index] |= dividendArg[index] << shift;
}
if (dividendBuffer[dividendSize] > 0)
++dividendSize;
dividend = dividendBuffer.data();

divisorBuffer.resize(divisorSize + 1);
for (size_t i = 0; i < divisorSize; ++i) {
size_t index = divisorSize - 1 - i;
divisorBuffer[index + 1] |= divisorArg[index] >> (BITS - shift);
divisorBuffer[index] |= divisorArg[index] << shift;
}
assert(divisorBuffer[divisorSize] == 0u);
divisor = divisorBuffer.data();
}
assert((divisor[divisorSize - 1] >> (BITS - 1)) == 1u);
vector<Limb> value(divisorSize + 1);
copy(dividend + dividendSize - divisorSize, dividend + dividendSize,
 value.begin());
const Limb* dividendPosition = dividend + dividendSize - divisorSize;
Limb* quotientPosition = quotient + dividendSize - divisorSize;
if (compareImpl(value.data(), divisorSize, divisor, divisorSize) < 0) {
assert(dividendPosition != dividend);
--dividendPosition;
--quotientPosition;
for (size_t i = divisorSize; i > 0; --i)
value[i] = value[i - 1];
value[0] = *dividendPosition;
}
while (true) {
assert(value[divisorSize] <= divisor[divisorSize - 1]);
bool divisionOverflow =
value[divisorSize] == divisor[divisorSize - 1];
Limb quot;
Limb rem;
if (divisionOverflow) {
quot = 0;
rem = value[divisorSize - 1];
} else {
divideShort(value[divisorSize - 1], value[divisorSize],
divisor[divisorSize - 1], quot, rem);
}
while (true) {
bool overestimated = divisionOverflow;
if (!divisionOverflow) {
Limb leftHigh;
Limb leftLow;
multiplyShort(quot, divisor[divisorSize - 2],
leftLow, leftHigh);
Limb rightHigh = rem;
Limb rightLow = value[divisorSize - 2];
if (leftHigh > rightHigh ||
(leftHigh == rightHigh && leftLow > rightLow)) {
overestimated = true;
}
}
if (!overestimated)
break;
--quot;
bool carry;
rem = addShort(rem, divisor[divisorSize - 1], carry);
if (carry)
break;
divisionOverflow = false;
}
vector<Limb> product(divisorSize + 1);
multiplyImpl(divisor, divisorSize, &quot, 1, product.data());
bool borrow = subtractImpl(value.data(), product.data(),
 divisorSize + 1);
if (borrow) {
bool carry = addImpl(value.data(), divisor, divisorSize);
assert(carry);
--quot;
}
assert(value[divisorSize] == 0u);
*quotientPosition = quot;
if (dividendPosition == dividend)
break;
--dividendPosition;
--quotientPosition;
for (size_t i = divisorSize; i > 0; --i)
value[i] = value[i - 1];
value[0] = *dividendPosition;
}
if (shift > 0) {
assert(((value[0] << (BITS - shift)) >> (BITS - shift)) == 0u);
for (size_t i = 0; i < divisorSize - 1; ++i)
value[i] =
(value[i] >> shift) | (value[i + 1] << (BITS - shift));
value[divisorSize - 1] = value[divisorSize - 1] >> shift;
}
copy(value.begin(), value.begin() + divisorSize, remainder);
}

static unsigned int countLeadingZeros(Limb value) {
assert(value > 0u);
return countLeadingZerosImpl(value);
}
static unsigned int countLeadingZerosImpl(unsigned int value) {
return static_cast<unsigned int>(__builtin_clz(value));
}
static unsigned int countLeadingZerosImpl(unsigned long value) {
return static_cast<unsigned int>(__builtin_clzl(value));
}
static unsigned int countLeadingZerosImpl(unsigned long long value) {
return static_cast<unsigned int>(__builtin_clzll(value));
}

static constexpr Limb MAX = numeric_limits<Limb>::max();
static constexpr size_t BITS = sizeof(Limb) * 8;

std::vector<Limb> limbs_;
Sign sign_;
};

template <typename T, typename = EnsureIntegral<T>>
bool operator==(const Int& left, T right) { return left == Int(right); }
template <typename T, typename = EnsureIntegral<T>>
bool operator==(T left, const Int& right) { return Int(left) == right; }
template <typename T, typename = EnsureIntegral<T>>
bool operator!=(const Int& left, T right) { return left != Int(right); }
template <typename T, typename = EnsureIntegral<T>>
bool operator!=(T left, const Int& right) { return Int(left) != right; }
template <typename T, typename = EnsureIntegral<T>>
bool operator<(const Int& left, T right) { return left < Int(right); }
template <typename T, typename = EnsureIntegral<T>>
bool operator<(T left, const Int& right) { return Int(left) < right; }
template <typename T, typename = EnsureIntegral<T>>
bool operator>(const Int& left, T right) { return left > Int(right); }
template <typename T, typename = EnsureIntegral<T>>
bool operator>(T left, const Int& right) { return Int(left) > right; }
template <typename T, typename = EnsureIntegral<T>>
bool operator<=(const Int& left, T right) { return left <= Int(right); }
template <typename T, typename = EnsureIntegral<T>>
bool operator<=(T left, const Int& right) { return Int(left) <= right; }
template <typename T, typename = EnsureIntegral<T>>
bool operator>=(const Int& left, T right) { return left >= Int(right); }
template <typename T, typename = EnsureIntegral<T>>
bool operator>=(T left, const Int& right) { return Int(left) >= right; }

template <typename T, typename = EnsureIntegral<T>>
Int operator+(const Int& augend, T addend) { return augend + Int(addend); }
template <typename T, typename = EnsureIntegral<T>>
Int operator+(T augend, const Int& addend) { return Int(augend) + addend; }
template <typename T, typename = EnsureIntegral<T>>
Int operator-(const Int& minuend, T subtrahend) {
return minuend - Int(subtrahend);
}
template <typename T, typename = EnsureIntegral<T>>
Int operator-(T minuend, const Int& subtrahend) {
return Int(minuend) - subtrahend;
}
template <typename T, typename = EnsureIntegral<T>>
Int operator*(const Int& multiplicand, T multiplier) {
return multiplicand * Int(multiplier);
}
template <typename T, typename = EnsureIntegral<T>>
Int operator*(T multiplicand, const Int& multiplier) {
return Int(multiplicand) * multiplier;
}
template <typename T, typename = EnsureIntegral<T>>
Int operator/(const Int& dividend, T divisor) {
return dividend / Int(divisor);
}
template <typename T, typename = EnsureIntegral<T>>
Int operator/(T dividend, const Int& divisor) {
return Int(dividend) / divisor;
}
template <typename T, typename = EnsureIntegral<T>>
Int operator%(const Int& dividend, T divisor) {
return dividend % Int(divisor);
}
template <typename T, typename = EnsureIntegral<T>>
Int operator%(T dividend, const Int& divisor) {
return Int(dividend) % divisor;
}

template <typename OStream>
OStream& operator<<(OStream& out, const Int& value) {
return value.serialize(out);
}
template <typename IStream>
IStream& operator>>(IStream& in, Int& value) {
string s;
in >> s;
value = Int(s);
return in;
}

constexpr Int::Limb Int::MAX;
constexpr size_t Int::BITS;

// END INT IMPLEMENTATION
// ****************************************************************************

int main()
{
    Int A, B;
    cin >> A >> B;
    cout << A % B << '\n';

    return 0;
}



Measured memory_bytes: 3228