//#pragma comment(linker, "/STACK:1024000000,1024000000") #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,l,r) for(i = l; i <= r; i++) #define red(i,l,r) for(i=(l);i>=(r);i--) #define u_long unsigned long long #define fff(i, u) for(i = head[u]; i != -1; i = nxt[i]) #define fin() freopen("in.txt", "r", stdin) #define fout() freopen("out.txt", "w", stdout) #define clr(vis, a) memset(vis, a, sizeof(vis)) #define LL long long #define ls id << 1 #define rs id << 1 | 1 #define lson id << 1, l, mid #define rson id << 1 | 1, mid + 1, r #define mid ( (l + r) >> 1 ) #define pb push_back #define mp make_pair #define pii pair #define X first #define Y second #define eps 1e-9 #define pi acos(-1) const int maxn = 2e5 + 10; const int maxm = maxn * 4 + 10; const int inf = 1e9; const LL mod = 1000000009; int getint() { char c; while((c = getchar()) && !(c >= '0' && c <= '9') && c != '-'); int ret = c - '0', sgn = 0; if(c == '-') sgn = 1, ret = 0; while((c = getchar()) && c >= '0' && c <= '9') ret = ret * 10 + c - '0'; if(sgn) ret = -ret; return ret; } LL xpow(LL x, LL k, LL mo){ LL ret = 1; while(k >= 1){ if(k & 1) ret = ret * x % mo; x = x * x % mo; k >>= 1; } return ret; } const int maxl = 50; const int bitlen = 9; char buffer[maxl * bitlen + 10]; const int MAXL = 1000000000; //10^9 LL tmp[bitlen * maxl]; LL q[bitlen * maxl]; struct Bignum { int a[maxl]; int sz; bool read(); Bignum() { memset(a, 0, sizeof(a)); sz = 1; } Bignum(u_long x); Bignum(const Bignum&); int cmp(const Bignum&bg) const; bool operator<(const Bignum&bg) const { return cmp(bg) < 0; } bool operator==(const Bignum&bg) const { return cmp(bg) == 0; } bool operator<=(const Bignum&bg) const { return cmp(bg) <= 0; } bool operator>(const Bignum&bg) const { return cmp(bg)>0; } bool operator>=(const Bignum&bg) const { return cmp(bg) >= 0; } bool operator!=(const Bignum&bg) const { return cmp(bg) != 0; } bool Try_sub(char *s,char *t,int lent,int lens); Bignum& operator = (const Bignum&bg); Bignum& operator += (const Bignum&bg); Bignum & operator -= (const Bignum& bg); Bignum& operator *= (const Bignum& bg); Bignum& operator /= (const Bignum& bg); Bignum& operator /= (int x); int operator % (int x); Bignum operator + (const Bignum&bg) const { return Bignum(*this) += bg; } Bignum operator / (const Bignum& bg) const { return Bignum(*this) /= bg; } Bignum operator * (const Bignum& bg) const { return Bignum(*this) *= bg; } Bignum operator - (const Bignum&bg) const { return Bignum(*this) -= bg; } Bignum operator%(const Bignum&bg) const { return *this - *this / bg * bg; } Bignum operator / (int x) const { return Bignum(*this) /= x; } Bignum pow(LL x); void output() const { printf("%d", a[sz - 1]); for (int i = sz - 2; i >= 0; --i) printf("%09d", a[i]); printf("\n"); } }a[4]; bool Bignum::read() { memset(a, 0, sizeof(a)); sz = 0; if (scanf("%s", buffer) != 1) return false; int n = strlen(buffer); int i; for (i = n - 1; i >= 0; i -= bitlen) { u_long x = 0, y = 1; for (int j = i; j > i - bitlen && j >= 0; --j) { x += y * (buffer[j] - '0'); y *= 10; } a[sz++] = x; } return true; } Bignum::Bignum(u_long x) { memset(a, 0, sizeof(a)); sz = 0; if (x == 0) sz = 1; while (x != 0) { a[sz++] = x % MAXL; x /= MAXL; } } Bignum::Bignum(const Bignum& bg) { sz = bg.sz; memcpy(a,bg.a,sizeof(a)); } int Bignum::cmp(const Bignum&bg) const { if (sz>bg.sz) return 1; else if (sz < bg.sz) return -1; for (int i = sz-1; i >= 0; --i) if (a[i] < bg.a[i]) return -1; else if (a[i] > bg.a[i]) return 1; return 0; } Bignum& Bignum::operator=(const Bignum& bg) { sz = bg.sz; memcpy(a,bg.a,sizeof(a)); return *this; } Bignum& Bignum::operator += (const Bignum& bg) { sz = max(sz, bg.sz); for (int i = 0; i < sz; ++i) { a[i] += bg.a[i]; a[i + 1] += a[i] / MAXL; a[i] %= MAXL; } while (a[sz] != 0) ++sz; return *this; } Bignum& Bignum::operator -= (const Bignum& bg) { for (int i = 0; i < sz; ++i) { a[i] -= bg.a[i]; if (a[i] < 0) { int j = i + 1; a[i] += MAXL; while (--a[j]<0) { a[j] += MAXL; ++j; } } } while (sz>1 && a[sz - 1] == 0) --sz; return *this; } bool Bignum::Try_sub(char * s,char * t,int lent,int lens) { if(lent>lens) return false; for(int i=0;i=0) continue; int j=i+1; s[i] += 10; while (j=lens) { ok=false; break; } } if(ok) return true; for(int i=0;i