#include<bitset>
#include<algorithm>
#include<iostream>
#include<string>
#include<deque>
using namespace std;
class int128;
void shift(int128 & in,deque<bool> & de);
template<size_t N>
bool operator<(bitset<N> const& b1,bitset<N> const& b2)
{
int i=N;
while( i-- && b1[i]==b2[i] ) { }
return ((-1 == i) ? false : (b1[i]<b2[i]));
}
class int128
{
bitset<128> number;
public:
explicit int128(string str):number(str){}
int128(bitset<128>const& b):number(b){}
int128(int a = 0 , int b = 0 , int c = 0 , int d = 0)
{
bitset<32> b1(a),b2(b),b3(c),b4(d);
int i, k = 128;
for(i = 32 ; i ; number[--k] = b1[--i]) { }
for(i = 32 ; i ; number[--k] = b2[--i]) { }
for(i = 32 ; i ; number[--k] = b3[--i]) { }
for(i = 32 ; i ; number[--k] = b4[--i]) { }
}
bool operator[](size_t i)const
{
return number[i];
}
bitset<128>::reference operator[](size_t i)
{
return number[i];
}
friend bool operator<(int128 const& i1,int128 const& i2)
{
return i1.number < i2.number;
}
friend int128 operator+(int128 const& i1,int128 const& i2)
{
if(i1 == 0)
return i2;
if(i2 == 0)
return i1;
int128 result;
bitset<2> sum;
for(int i = 0 ; i < 128 ; ++i)
{
sum=i1[i]+i2[i]+sum.to_ulong();
result[i]=sum[0];
sum>>=1;
}
return result;
}
friend int128 operator-(int128 const& i1,int128 const& i2)
{
if(i2==0)
return i1;
int128 result=i1;
for(int i = 0 ; i < 128 ; ++i)
{
if(i2[i] == 0) {}
else
{
if(result[i] == 1)
result[i] = 0;
else
{
int k = i;
while(k < 128 && result[k] == 0)
{
result[k] = 1;
++k;
}
if(k != 128)
result[k] = 0;
}
}
}
return result;
}
friend int128 operator*(int128 const& i1,int128 const& i2)
{
if(i1==0 || i2==0)
return int128();
if(i1==1)
return i2;
if(i2==1)
return i1;
int128 acc=int128();
for(int i=0;i<128;++i)
{
if(i2[i]==1)
{
acc=acc+(i1<<i);
}
}
return acc;
}
friend int128 operator/(int128 const& i1,int128 const& i2)
{
if(i1 < i2)
return int128();
deque<bool> de;
bool flag = 0;
for(int i = 127 ; i >= 0 ; --i)
{
if(flag == 0 && i1[i] == 0) {}
else
{
flag = 1;
de.push_back(i1[i]);
}
}
int128 div = int128();
int128 result = int128();
while(!de.empty())
{
shift(div,de);
if(div < i2)
{
result = result<<1;
}
else
{
result = (result<<1) + int128(0,0,0,1);
div = div - i2;
}
}
return result;
}
friend int128 operator%(int128 const& i1,int128 const& i2)
{
if(i1 < i2)
return i1;
deque<bool> de;
bool flag = 0;
for(int i = 127 ; i >= 0 ; --i)
{
if(flag == 0 && i1[i] == 0) {}
else
{
flag = 1;
de.push_back(i1[i]);
}
}
int128 div = int128();
int128 result = int128();
while(!de.empty())
{
shift(div,de);
if(div < i2)
{
result = result<<1;
}
else
{
result = (result<<1) + int128(0,0,0,1);
div = div - i2;
}
}
return div;
}
friend bool operator==(int128 const& i,int const k)
{
bitset<32> bb(k);
for(int g = 0 ; g < 32 ; ++g)
{
if(i[g] != bb[g])
return 0;
}
return 1;
}
void operator=(bitset<128>const& b)
{
number = b;
}
friend ostream& operator<<(ostream& o,int128 const& i)
{
o<<i.number;
return o;
}
int128 operator<<(size_t step)const
{
return int128(number<<step);
}
unsigned long to_ulong()const
{
return *((unsigned long*)&number);
}
public:
bool ToDecimalStr(std::string &str)
{
str.clear();
char buf[128] = {0};
int128 Radix(0, 0, 0, 10);
for(int128 num = number; !(num == 0); num = num/Radix)
{
if( sprintf_s(buf, 64, "%d", ((int)(num%Radix).to_ulong())) < 0 )
{
return false;
}
str = buf + str;
}
return true;
}
static void Print(int128 & data, bool bEndl = true)
{
string str;
if( data.ToDecimalStr(str) )
{
printf("%s%s", str.c_str(), (bEndl?"\n":""));
}
}
};
static int128 const one = int128(0,0,0,1);
template<size_t N>
void add_one(bitset<N>& b)
{
int i = 0;
while(i < N && b[i] == 1)
{
b[i] = 0;
++i;
}
if(i == N)
return;
b[i] = 1;
}
void add_one(int128& k)
{
int i = 0;
while(i < 128 && k[i] == 1)
{
k[i] = 0;
++i;
}
if(i == 128)
return;
k[i] = 1;
}
void shift(int128 & in,deque<bool> & de)
{
if(de.front()==1)
{
de.pop_front();
in=(in<<1)+one;
}
else
{
de.pop_front();
in=in<<1;
}
}
bool IsPrime(int128 const& number)
{
for(int128 i = int128(0,0,0,2) ; i < number ; add_one(i))
{
if(number%i == 0)
return 0;
}
return 1;
}