// #include<bits/stdc++.h>拆分：
#include<iostream>
#include <algorithm>
#include <math.h>
#include <cmath>
#include<string>
#include<cstring>
#include<list>
#include<map>
#include<queue>
#include<iterator>
#include<stack>
#include<cstdio>
#include <type_traits>
#include <functional>
#include <tuple>
#include <random>
#include <cstdint>
#include <unistd.h>
#include <vector>
#include <sstream>
#include <stdexcept>
#include <memory>
#include <numeric>
#include<list>
#include<map>
#include<queue>
#include<iterator>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <locale>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <shared_mutex>
#include <bit>
#include <version>
#include<assert.h>
#include <ctype.h>
#include <errno.h>
#include <float.h>
using namespace std;
int an[10010],bn[10010],cn[10010];
string s1,s2;
void stoh(string s,int h[]){
h[0]=s.size();
for(int i=1,j=s.size()-1;i<=h[0];i++,j--)h[i]=s[j]-'0';
}
void add(int a[],int b[],int c[]){
c[0]=max(a[0],b[0]);
for(int i=1;i<=c[0];i++){
c[i+1]=(a[i]+b[i]+c[i])/10;
c[i]=(a[i]+b[i]+c[i])%10;
}
if(c[c[0]+1]>0)c[0]++;
}
void print(int x[]){
for(int i=x[0];i>=1;i--)cout<<x[i];
}
void solve1(){
cin>>s1>>s2;
stoh(s1,an),stoh(s2,bn),add(an,bn,cn),print(cn);
}
const double PI=4*atan(1);
template<typename T>
void Swap(T &a,T &b){
T c=a;
a=b;
b=c;
return;
}
template<typename T>
T Max(const T &a,const T &b){
return a<b?b:a;
}
typedef long long ll;
struct comp{
double real,imag;
comp operator+(const comp &x)const{
return {real+x.real,imag+x.imag};
}
comp operator-(const comp &x)const{
return {real-x.real,imag-x.imag};
}
comp operator*(const comp &x)const{
return {realx.real-imagx.imag,realx.imag+x.realimag};
}
comp operator/(const unsigned &x)const{
return {real/(double)x,imag/(double)x};
}
};
void FFT(comp f,unsigned n,int rev){
for(unsigned i=1,j=n>>1,k;i<n-1;i++){
if(i<j)
Swap(f[i],f[j]);
k=n>>1;
while(j>=k){
j-=k;
k>>=1;
}
j+=k;
}
for(unsigned l=2;l<=n;l<<=1){
double arg=2PIrev/l;
comp wn={cos(arg),sin(arg)};
for(unsigned i=0;i<n;i+=l){
comp w={1,0};
for(unsigned j=0;j<(l>>1);j++){
comp f1=f[i+j];
comp f2=f[i+j+(l>>1)];
f[i+j]=f1+wf2;
f[i+j+(l>>1)]=f1-wf2;
w=wwn;
}
}
}
if(!~rev)
for(unsigned i=0;i<n;i++)
f[i]=f[i]/n;
}
#define BASE 100
template<const unsigned Size>
class bigint{
private:
unsigned len;
int num[Size];
void init(){
memset(num,0,sizeof(num));
len=1;
}
bool abs_greater_equal(const bigint &a)const{
if(len!=a.len)
return len>a.len;
for(int i=len;i;i--)
if(num[i]!=a.num[i])
return num[i]>a.num[i];
return 1;
}
public:
bigint(){
init();
}
void get_num(std::string s){
init();
int f=0;
unsigned slen=s.length();
if(s[0]'-')
num[0]=f=1;
len=0;
unsigned temp=0,w=1;
for(int i=slen-1;i>=f;i--){
temp+=(s[i]^48)*w;
w=(w<<1)+(w<<3);
if(wBASE||if){
num[++len]=(int)temp;
temp=0;
w=1;
}
}
if(temp||len0)
num[len]=temp;
}
bool operator<(const bigint &a)const{
if(num[0]&&!a.num[0])
return 1;
if(!num[0]&&a.num[0])
return 0;
if(num[0]){
if(len!=a.len)
return len>a.len;
for(int i=len;i;i--)
if(num[i]!=a.num[i])
return num[i]>a.num[i];
}
else{
if(len!=a.len)
return len<a.len;
for(int i=len;i;i--)
if(num[i]!=a.num[i])
return num[i]<a.num[i];
}
return 0;
}
bigint operator+(const bigint &a)const{
bigint res;
if(len==1&&num[1]0){
res=a;
return res;
}
if(a.len1&&a.num[1]==0){
res=*this;
return res;
}
if(num[0]==a.num[0]){
res.num[0]=num[0];
unsigned len_sum=1;
while(len_sum<len+a.len)
len_sum<<=1;
comp *fa=new complen_sum;
comp *fb=new complen_sum;
for(unsigned i=0;i<len;i)
fa[i]={(double)num[i+1],0};
for(unsigned i=0;i<a.len;i++)
fb[i]={(double)a.num[i+1],0};
FFT(fa,len_sum,1);
FFT(fb,len_sum,1);
for(unsigned i=0;i<len_sum;i++)
fa[i]=fa[i]+fb[i];
FFT(fa,len_sum,-1);
res.len=Max(len,a.len);
ll temp=0;
for(unsigned i=0;i<res.len;i++){
ll val=(ll)round(fa[i].real)+temp;
res.num[i+1]=(int)(val%BASE);
temp=val/BASE;
}
if(temp)
res.num[res.len]=temp;
while(res.len>1&&res.num[res.len]==0)
res.len--;
delete[] fa;
delete[] fb;
}
else{
if(abs_greater_equal(a)){
res.num[0]=num[0];
unsigned len_sum=1;
while(len_sum<len+a.len)
len_sum<<=1;
comp *fa=new complen_sum;
comp *fb=new complen_sum;
for(unsigned i=0;i<len;i)
fa[i]={(double)num[i+1],0};
for(unsigned i=0;i<a.len;i++)
fb[i]={(double)a.num[i+1],0};
FFT(fa,len_sum,1);
FFT(fb,len_sum,1);
for(unsigned i=0;i<len_sum;i++)
fa[i]=fa[i]-fb[i];
FFT(fa,len_sum,-1);
res.len=Max(len,a.len);
ll temp=0;
for(unsigned i=0;i<res.len;i++){
ll val=(ll)round(fa[i].real)+temp;
if(val<0){
val+=BASE;
temp=-1;
}
else
temp=0;
res.num[i+1]=(int)(val%BASE);
}
if(temp)
res.num[res.len]=temp;
while(res.len>1&&res.num[res.len]==0)
res.len--;
delete[] fa;
delete[] fb;
}
else{
res.num[0]=a.num[0];
unsigned len_sum=1;
while(len_sum<len+a.len)
len_sum<<=1;
comp *fa=new complen_sum;
comp *fb=new complen_sum;
for(unsigned i=0;i<len;i)
fa[i]={(double)num[i+1],0};
for(unsigned i=0;i<a.len;i++)
fb[i]={(double)a.num[i+1],0};
FFT(fa,len_sum,1);
FFT(fb,len_sum,1);
for(unsigned i=0;i<len_sum;i++)
fa[i]=fb[i]-fa[i];
FFT(fa,len_sum,-1);
res.len=Max(len,a.len);
ll temp=0;
for(unsigned i=0;i<res.len;i++){
ll val=(ll)round(fa[i].real)+temp;
if(val<0){
val+=BASE;
temp=-1;
}
else
temp=0;
res.num[i+1]=(int)(val%BASE);
}
if(temp)
res.num[res.len]=temp;
while(res.len>1&&res.num[res.len]0)
res.len--;
delete[] fa;
delete[] fb;
}
if(res.len1&&res.num[1]0)
res.num[0]=0;
}
return res;
}
bigint operator*(const bigint &a)const{
bigint res;
if((len1&&num[1]0)||(a.len1&&a.num[1]==0))
return res;
res.num[0]=num[0]^a.num[0];
unsigned len_sum=1;
while(len_sum<len+a.len)
len_sum<<=1;
comp *fa=new complen_sum;
comp *fb=new complen_sum;
for(unsigned i=0;i<len;i)
fa[i]={(double)num[i+1],0};
for(unsigned i=0;i<a.len;i++)
fb[i]={(double)a.num[i+1],0};
FFT(fa,len_sum,1);
FFT(fb,len_sum,1);
for(unsigned i=0;i<len_sum;i++)
fa[i]=fa[i]*fb[i];
FFT(fa,len_sum,-1);
res.len=len+a.len;
ll temp=0;
};
const int N=1<<10,M=100;
int n,m;
bigint<114514> a,b,c;
void solve2(){
a.read();
b.read();
c=a+b;
c.print();
}
#define int long long
#define ull unsigned int
#define N 65536
int memory[N];
ull code[N] = {
0x0000000000000000, 0x0000000000000001, 0x5000000000010002, 0x1000000000000002, 0xf000000000000000
};
void solve3()
{
for(int i=0;;i=(i+1)%N)
{
int op=code[i]>>60;
if(op0) //Input
{
int p=code[i]&65535;
cin >> memory[ (code[i]>>56)&1 ? memory[p] : p ];
}
else if(op1) //Output
{
int p=code[i]&65535, val = memory[ (code[i]>>56)&1 ? memory[p] : p ];
if((code[i]>>57)&1)
{
cout<<char(val&127);
}
else
{
cout<<val;
}
}
else if(op2) //Write
{
int p = (code[i]>>32)&65535, val = code[i]&((1ll<<32)-1);
memory[ (code[i]>>56)&1 ? memory[p] : p ] = val;
}
else if(op3) //Copy
{
int pf = (code[i]>>16)&65535, pt = code[i]&65535;
int val = memory[ (code[i]>>55)&1 ? memory[pf] : pf ];
memory[ (code[i]>>56)&1 ? memory[pt] : pt ] = val;
}
else if(op4) //Calculate (& | ~ ^ << >>)
{
int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535;
int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ],
val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ], val3;
int op2 = (code[i]>>52)&15;
if(op20)
{
val3=val1&val2;
}
else if(op21)
{
val3=val1|val2;
}
else if(op22)
{
val3=~val2;
}
else if(op23)
{
val3=val1^val2;
}
else if(op24)
{
val3=((val2>>6)?0:val1<<val2);
}
else
{
val3=((val2>>6)?0:val1>>val2);
}
memory[ (code[i]>>56)&1 ? memory[p3] : p3 ] = val3;
}
else if(op5)
{
int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535;
int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ],
val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ], val3;
int op2 = (code[i]>>52)&15;
if(op20)
{
val3=val1+val2;
}
else if(op21)
{
val3=val1-val2;
}
else if(op22)
{
val3=val1*val2;
}
else if(op23)
{
val3=(val2?val1/val2:0);
}
else
{
val3=(val2?val1%val2:0);
}
memory[ (code[i]>>56)&1 ? memory[p3] : p3 ] = val3;
}
else if(op6) //Goto
{
int p=code[i]&65535;
i = (code[i]>>56)&1 ? memory[p] : p;
i = (i+N-1)%N;
}
else if(op7) //If-goto (> < == >= <= !=)
{
int p1 = (code[i]>>32)&65535, p2 = (code[i]>>16)&65535, p3 = code[i]&65535;
int val1 = memory[ (code[i]>>58)&1 ? memory[p1] : p1 ],
val2 = memory[ (code[i]>>57)&1 ? memory[p2] : p2 ];
int op2 = (code[i]>>52)&15;
bool flag;
if(op20)
{
flag=(val1>val2);
}
else if(op21)
{
flag=(val1<val2);
}
else if(op22)
{
flag=(val1val2);
}
else if(op23)
{
flag=(val1>=val2);
}
else if(op24)
{
flag=(val1<=val2);
}
else
{
flag=(val1!=val2);
}
if(flag)
{
i = (code[i]>>56)&1 ? memory[p3] : p3;
i = (i+N-1)%N;
}
}
else if(op8) //x++
{
int p=code[i]&65535;
memory[ (code[i]>>56)&1 ? memory[p] : p ]++;
}
else if(op9) //x--
{
int p=code[i]&65535;
memory[ (code[i]>>56)&1 ? memory[p] : p ]--;
}
else if(op15) //Exit
{
break;
}
else
{
cout<<"\n\nError: Invalid code\n\n";
}
}
}
signed main(void){
}
