#include
#include
using namespace std;
struct wint{
int arr[1001] = {},len = 1,nag = 1;
string getstr(){
string t = (nag ? "" : "-");
for(int i=1;i<=len;i++)
t += char(arr[i]+'0');
return t;
}
void init(long long data){
if(data < 0){
nag = 0;
data = -data;
}
len = 0;
while(data){
arr[++len] = data % 10;
data /= 10;
}
}
void init(string data){
if(data[0] == '-'){
nag = 0;
data = data.substr(1);
}
len = data.size();
for(int i=1;i<=len;i++)
arr[i] = data[i-1] - '0';
}
void input(){
string t;
cin >> t;
init(t);
}
void output(char end){
cout << getstr() << end;
}
void output(string end){
cout << getstr() << end;
}
void output(){
cout << getstr();
}
void clear(){
for(int i=1;i<=1000;i++)
arr[i] = 0;
len = 1;
nag = 1;
}
int getlen(){
return len;
}
void copyto(wint &other){
other.len = len;
other.nag = nag;
for(int i=1;i<=len;i++)
other.arr[i] = arr[i];
}
void copyas(wint other){
len = other.len;
nag = other.nag;
for(int i=1;i<=len;i++)
arr[i] = other.arr[i];
}
void reverse(){
for(int i=1;i<=len/2;i++)
swap(arr[i],arr[len-i+1]);
}
};
bool operator==(wint fir,wint sec){
if(fir.len != sec.len || fir.nag != sec.nag) return 0;
for(int i=1;i<=fir.len;i++)
if(fir.arr[i] != sec.arr[i]) return 0;
return 1;
}
bool operator!=(wint fir,wint sec){
return !(fir == sec);
}
bool operator<(wint fir,wint sec){
if(fir.nag < sec.nag) return 1;
if(fir.nag > sec.nag) return 0;
if(fir.len < sec.len) return 1;
if(fir.len > sec.len) return 0;
for(int i=1;i<=fir.len;i++){
if(fir.arr[i] > sec.arr[i]) return 0;
if(fir.arr[i] < sec.arr[i]) return 1;
}
return fir != sec;
}
bool operator<=(wint fir,wint sec){
return fir < sec || fir == sec;
}
bool operator>(wint fir,wint sec){
return !(fir <= sec);
}
bool operator>=(wint fir,wint sec){
return !(fir < sec);
}
void swap(wint &fir,wint &sec){
wint temp; temp.copyas(fir);
sec.copyto(fir),temp.copyto(sec);
}
wint max(wint fir,wint sec){
if(fir > sec) return fir;
else return sec;
}
wint min(wint fir,wint sec){
if(fir < sec) return fir;
else return sec;
}
wint plusnum(wint fir,wint sec){
wint ans,cfir,csec;
cfir.copyas(fir),csec.copyas(sec);
cfir.reverse(),csec.reverse();
bool pluser = 0;
ans.nag = max(fir,sec).nag;
ans.len = max(fir,sec).len;
if((fir.nag == 1 && sec.nag == 1) || (fir.nag == 0 && sec.nag == 0)){
for(int i=1;i<=ans.len;i++){
ans.arr[i] = cfir.arr[i] + csec.arr[i] + pluser;
pluser = ans.arr[i] / 10;
ans.arr[i] %= 10;
}
if(pluser) ans.arr[++ans.len] = 1;
}
else{
if(csec > cfir) swap(cfir,csec);
for(int i=1;i<=ans.len;i++){
ans.arr[i] = cfir.arr[i] - csec.arr[i] - pluser;
pluser = bool(ans.arr[i] < 0);
if(pluser) ans.arr[i] += 10;
}
while(ans.len > 1 && ans.arr[ans.len] == 0) ans.len--;
}
ans.reverse();
return ans;
}
wint minusnum(wint fir,wint sec){
wint csec,temp; csec.copyas(sec);
csec.nag = !csec.nag;
return plusnum(fir,csec);
}
wint timesnum(wint fir,wint sec){
wint ans,cfir,csec;
cfir.copyas(fir),csec.copyas(sec);
cfir.reverse(),csec.reverse();
ans.nag = !(cfir.nag ^ csec.nag);
ans.len = cfir.len + csec.len - 1;
for(int i=1;i<=cfir.len;i++){
int timeser = 0;
for(int j=1;j<=csec.len;j++){
ans.arr[i+j-1] += cfir.arr[i] * csec.arr[j] + timeser;
timeser = ans.arr[i+j-1] / 10;
ans.arr[i+j-1] %= 10;
}
if(timeser){
if(i + csec.len > ans.len) ans.len++;
ans.arr[i+csec.len] += timeser;
}
}
ans.reverse();
return ans;
}
pair<wint,wint> divmod(wint fir,wint sec){
wint c,t,f,temp;
int pos = sec.len+1;
while(fir >= sec){
t.arr[pos] = 1,t.len = pos;
c.copyas(timesnum(t,sec));
temp.init((long long)pos);
while(fir >= c){
fir.copyas(minusnum(fir,c));
f.copyas(plusnum(temp,f));
}
t.clear(),c.clear(),pos--;
}
return pair<wint,wint>{f,fir};
}
wint dividednum(wint fir,wint sec){
return divmod(fir,sec).first;
}
wint modnum(wint fir,wint sec){
return divmod(fir,sec).second;
}
int main(){
}
