#include <stdio.h>
#include <vector>
#include <string>
#include <cmath>
#define base 1000000000
#define base2 ((ull) base * base)
#define KARATSUBA 111
#define fix(x) {x.resize(x[0]+3); x[x[0]+1]=x[x[0]+2]=0;}
#define ull unsigned long long
using namespace std;
class BigInt{
public:
vector <unsigned> a; //la final nu il las public
int semn; //merge si char dar asa un BigInt are 16 byte, alinierea e mai buna
BigInt();
BigInt(long long nr);
// nu merge bine pentru ca apar ambiguitati
// operator long long() const;
BigInt& operator+=(const BigInt &b); //incrementare cu un alt numar mare
BigInt& operator+=(long long k); //incrementare cu orice intreg, in afara de unsigned long long > 2^63 (yeah, right)
friend BigInt operator+(const BigInt &x, const BigInt &y);
friend BigInt operator-(const BigInt &x, const BigInt &y);
BigInt& operator*=(int k);
friend BigInt operator*(const BigInt &x, const BigInt &y);
friend BigInt operator/(const BigInt &x, const BigInt &y);
friend BigInt operator%(const BigInt &x, const BigInt &y);
BigInt& operator/=(int k);
int operator%(int k);
int operator==(const BigInt &x) const;
int operator!=(const BigInt &x) const;
int operator<(const BigInt &x) const;
int operator<=(const BigInt &x) const;
int operator>(const BigInt &x) const;
int operator>=(const BigInt &x) const;
void shr(unsigned k);
void shl(unsigned k);
void write(FILE *f) const;
void read(FILE *f);
};
BigInt::BigInt()
{
a.resize(4);
a[0]=1;
}
BigInt::BigInt(long long nr)
{
if (nr<0) semn=-1, nr=-nr;
unsigned long long k=nr;
a.resize(1);
a[0]=0;
while (k>=base) a.push_back(k%base), k/=base;
a.push_back(k);
a[0]=a.size()-1;
fix(a);
}
/*
BigInt::operator long long() const
{
long long nr=a[2]*(ull)base+a[1];
return nr*semn;
}
*/
void BigInt::shr(unsigned k)
{
if (k>a[0]) k=a[0];
unsigned i;
for (i=1; i<=a[0]-k; i++)
a[i]=a[i+k];
a[0]-=k;
if (!a[0]) a[0]=1, a[1]=1;
fix(a);
}
void BigInt::shl(unsigned k)
{
unsigned i;
a[0]+=k;
a.resize(a[0]+2);
for (i=a[0]; i>k; i--)
a[i]=a[i-k];
memset(&a[1], 0, 4*k);
}
BigInt& BigInt::operator+=(const BigInt &b)
{
if (this == &b){ //in cazul ca in care fac a+=a;
unsigned i, n=a[0]+1;
if (n<=a.size()) a.resize(n+1);
for (i=1; i<n; i++)
a[i]+=a[i];
for (i=1; i<n; i++)
if (a[i]>=base) a[i]-=base, a[i+1]++;
if (a[n]) a[0]++;
return *this;
}
unsigned i, n=b.a[0]+1;
if (n>=a.size()) a.resize(n+1);
for (i=1; i<n; ++i)
if (a[i]+b.a[i]>=base) a[i]+=(b.a[i]-base), a[i+1]++; else a[i]+=b.a[i];
if (a[n]) n++;
if (n-1>a[0]) a[0]=n-1;
fix(a);
return *this;
}
BigInt operator+(const BigInt &x, const BigInt &y)
{
BigInt rez;
const unsigned *a, *b;
if (x.a[0]>y.a[0]) a=&x.a[0], b=&y.a[0]; else a=&y.a[0], b=&x.a[0];
unsigned n=a[0]+1, m=b[0]+1;
rez.a.resize(a[0]+2);
memcpy(&rez.a[0], a, sizeof(unsigned) * (n+1));
for (unsigned i=1; i<m; i++){
rez.a[i]+=b[i];
if (rez.a[i]>=base) rez.a[i]-=base, ++rez.a[i+1];
}
unsigned k=m;
while (rez.a[k]>=base) rez.a[k]-=base, ++k, ++rez.a[k];
if (rez.a[a[0]+1]) rez.a[0]++;
fix(rez.a);
return rez;
}
BigInt operator-(const BigInt &x, const BigInt &y)
{
BigInt rez; //trebuie ca x>=y deocamdata
const unsigned *a = &x.a[0], *b = &y.a[0];
unsigned n=a[0]+1, m=b[0]+1;
rez.a.resize(a[0]+3);
memcpy(&rez.a[0], a, sizeof(unsigned) * (n+1));
for (unsigned i=1; i<m; i++){
if (rez.a[i]>base) rez.a[i]+=base, --rez.a[i+1];
rez.a[i]-=b[i]; //daca face underflow
if (rez.a[i]>base) rez.a[i]+=base, --rez.a[i+1];
}
unsigned k=m;
while (rez.a[k]>base) rez.a[k]+=base, ++k, --rez.a[k];
while (!rez.a[rez.a[0]] && rez.a[0]>1) rez.a[0]--;
fix(rez.a);
return rez;
}
BigInt& BigInt::operator+=(long long nr)
{
fix(a);
if (a.size()<5) a.resize(5);
ull k = nr, poz=1;
while (k>=base){
a[poz]+=k%base;
k/=base;
if (a[poz]>=base) a[poz]-=base, ++a[poz+1];
poz++;
}
a[poz]+=k;
if (a[poz]>=base) a[poz]-=base, ++a[poz+1];
if (a[a[0]+1]) a[0]++;
fix(a);
return *this;
}
BigInt& BigInt::operator*=(int nr)//sa nu fie prea mare numarul k, pana in 10^9
{
if (nr<0) semn=-semn, nr=-nr;
ull num, k=nr;
unsigned i, n=a[0]+1;
vector <unsigned> sol(a.size()+1);
for (i=1; i<n; i++){
num=a[i] * k;
unsigned cat = num/base;
sol[i]+=num - cat*(ull)base;
sol[i+1]+=cat;
if (sol[i]>=base) sol[i]-=base, sol[i+1]++;
}
sol[0]=a[0];
a=sol;
if (a[a[0]+1]) a[0]++;
while (a[0]>1 && !a[a[0]]) --a[0];
fix(a);
return *this;
}
BigInt operator*(const BigInt &x, const BigInt &y)
{
const unsigned *a, *b;
if (x.a[0]>y.a[0]) a=&x.a[0], b=&y.a[0]; else a=&y.a[0], b=&x.a[0];
unsigned n=a[0]+1, m=b[0]+1, i, j, k;
unsigned limit=75*n/100;
if (m>KARATSUBA && m<limit){
m--; n--;
BigInt rez, A, B;
A.a.resize(m+3);
rez.a.resize(n+m+3);
const BigInt *C;
if (x.a[0]>y.a[0]) C=&y; else C=&x;
A.a[0]=m;
k=1;
while (k<=n){
if (k+m-1>n){
A.a[0]=n-k+1; fix(A.a);
}
memcpy(&A.a[1], a+k, 4*A.a[0]);
B=A*(*C);
for (i=1; i<=B.a[0]; i++){
rez.a[i+k-1]+=B.a[i];
if (rez.a[i+k-1]>=base) rez.a[i+k-1]-=base, ++rez.a[i+k];
}
k+=m;
}
n+=m;
while (n>1 && !rez.a[n]) --n;
rez.a[0]=n;
rez.semn=x.semn*y.semn;
fix(rez.a);
return rez;
}
if (n>KARATSUBA && m>=limit){ //Karatsuba
BigInt x1, x2, y1, y2, A, B, C;
unsigned p=(n+m)/4;
x2.a.resize(p+4);
x2.a[0]=p;
memcpy(&x2.a[1], a+1, 4*p);
x1.a.resize(n-p+4);
x1.a[0]=n-p-1;
memcpy(&x1.a[1], a+p+1, 4*(n-p-1));
y2.a.resize(p+4);
y2.a[0]=p;
memcpy(&y2.a[1], b+1, 4*p);
y1.a.resize(m-p+4);
y1.a[0]=m-p-1;
memcpy(&y1.a[1], b+p+1, 4*(m-p-1));
A=x1*y1;
B=x2*y2;
C=(x1+x2)*(y1+y2)-A-B;
A.shl(2*p);
memcpy(&A.a[1], &B.a[1], sizeof(int)*2*p);
C.shl(p);
A+=C;
A.semn=x.semn*y.semn;
fix(A.a);
return A;
}
vector <ull> sol(n+m+1);
sol[0]=n+m-3;
for (i=1; i<m; i++)
for (j=1, k=i; j<n; ){
#define W sol[k] += (ull) b[i] * a[j++]; if (sol[k]>=base2) sol[k]-=base2, ++sol[k+2]; k++;
W W W
}
BigInt rez;
rez.a.resize(sol[0]+3);
for (i=0; i<n+m; i++)
if (sol[i]>=base2) sol[i]-=base2, ++sol[i+2];
for (i=0; i<n+m; i++){
register unsigned cat=sol[i]/base;
sol[i+1]+=cat;
rez.a[i]=sol[i]-cat*(ull)base;
}
if (rez.a[rez.a[0]+1]) rez.a[0]++;
fix(rez.a);
rez.semn=x.semn * y.semn;
return rez;
}
BigInt& BigInt::operator/=(int nr)
{
if (nr<0) semn=-semn, nr=-nr;
ull num=0;
const unsigned k=nr;
for (unsigned i=a[0]; i; i--){
num=a[i] + num*base;
a[i]=num/k;
num%=k;
}
while (!a[a[0]] && a[0]>1) a[0]--;
fix(a);
return *this;
}
int BigInt::operator%(int nr)
{
ull num=0;
const unsigned k=nr;
for (unsigned i=a[0]; i; i--){
num=a[i] + num*base;
a[i]=num/k;
num%=k;
}
return num;
}
BigInt operator/(const BigInt &x, const BigInt &y)
{
if (x<y) return 0;
unsigned n=x.a[0], m=y.a[0];
const unsigned *a=&x.a[0];
BigInt nr=0, cat, rez;
rez.a.resize(n+3);
nr.a.resize(m+4);
unsigned i,j;
nr.a[0]=m-1;
for (i=m-1; i>0; i--)
nr.a[i]=x.a[n-m+i+1];
for (i=n-m+1; i>0; i--){
nr.a[0]++;
for (j=nr.a[0]; j>1; j--)
nr.a[j]=nr.a[j-1];
nr.a[1]=a[i];
while (nr.a[0]>1 && !nr.a[nr.a[0]]) --nr.a[0];
if (nr<y){
rez.a[i]=0; continue;
}
unsigned p,u;
long double num1=(long double) base * nr.a[m+1] + (long double)nr.a[m];
long double num2=(long double) y.a[m];
if (m>1){
num1=num1*base + (long double) nr.a[m-1];
num2=num2*base + (long double) y.a[m-1];
}
p=(unsigned) (num1/(num2+1));
if (p<0) p=0;
cat=y;
cat*=p;
u = (unsigned) ((num1+1)/(num2-1));
if (u>p && cat+y<=nr) cat+=y, ++p;
nr=nr-cat;
rez.a[i]=p;
}
while (n>1 && !rez.a[n]) --n;
rez.a[0]=n;
fix(rez.a);
rez.semn=x.semn*y.semn;
return rez;
}
BigInt operator%(const BigInt &x, const BigInt &y)
{
BigInt cat=x/y;
return x-y*cat;
}
int BigInt::operator==(const BigInt &x) const
{
for (int i=0; i<=a[0]; i++)
if (x.a[i]!=a[i]) return 0;
return 1;
}
int BigInt::operator!=(const BigInt &x) const
{
return !(*this == x);
}
int BigInt::operator<(const BigInt &x) const
{
if (a[0]<x.a[0]) return 1;
if (a[0]>x.a[0]) return 0;
unsigned k=a[0];
while (x.a[k]==a[k] && k) k--;
return (a[k]<x.a[k]);
}
int BigInt::operator<=(const BigInt &x) const
{
if (a[0]<x.a[0]) return 1;
if (a[0]>x.a[0]) return 0;
unsigned k=a[0];
while (x.a[k]==a[k] && k) k--;
return (a[k]<=x.a[k]);
}
int BigInt::operator>(const BigInt &x) const
{
return !(*this <= x);
}
int BigInt::operator>=(const BigInt &x) const
{
return !(*this < x);
}
void BigInt::write(FILE *f) const
{
int i,n=a[0];
if (semn==-1) fprintf(f, "-1");
fprintf(f, "%u", a[n]);
for (i=n-1; i>0; i--)
fprintf(f, "%.9u", a[i]);
printf("\n");
}
void BigInt::read(FILE *f)
{
char c=0;
while (c<'0' || c>'9') c=fgetc(f); //trebuie sa fie sigur ca e un numar de citit aici
string s="000000000";
while (c>='0' && c<='9') s+=c, c=fgetc(f);
int i, j, n=s.length()/9, lung=s.length()%9;
a.resize(n+2);
memset(&a[0], 0, sizeof(unsigned)*(n+2));
if (!lung) lung=9, n--;
for (i=1; i<=n; i++)
for (j=lung; j<lung+9; j++)
a[i]=a[i]*10 + (s[(n-i)*9+j]-'0');
a[0]=n;
while (!a[a[0]] && a[0]>0) a[0]--;
fix(a);
}
BigInt pow(BigInt &a, int nr)
{
BigInt rez=1;
for (int p=(1<<22); p>0; p/=2){
rez=rez*rez;
if (nr&p) rez=rez*a;
}
return rez;
}
BigInt fibo(unsigned n)
{
BigInt a=1, b=1, f1, f3;
unsigned p=1<<30, k=0;
while (p>n) p/=2;
p/=2; k=2;
if (p && (n&p)) b=2, ++k;
for (p/=2; p>1; p/=2){
a=a*a;
b=b*b;
f3=4*b-a;
if (k&1) f3.a[1]-=2; else f3.a[1]+=2;
k*=2;
if (n&p) k++;
f1=a+b;
if (n&p) b=f3, a=f3-f1;
else b=f3-f1, a=f1;
}
if (p){
if (n&1){
b += b;
b = (b+a)*(b-a);
if (k&1) b.a[1]-=2; else b.a[1]+=2;
} else b=b*(b+a+a);
}
return b;
}
BigInt a,b,c;
int main()
{
freopen("next.in", "r", stdin);
freopen("next.out", "w", stdout);
a.read(stdin);
b.read(stdin);
c=a%b;
if(c>0)
{
b=b-c;
a+=b;
}
a.write(stdout);
return 0;
}