#line 1 "code.cpp" #pragma GCC optimize("Ofast") #pragma GCC target("avx") #pragma GCC optimize("unroll-loops") #line 2 "library/template/template.hpp" #include #line 3 "library/template/macro.hpp" #define SELECT4(a,b,c,d,e,...) e #define SELECT3(a,b,c,d,...) d #define REP1(a) for(ll i=0;i<(ll)(a);++i) #define REP2(i,a) for(ll i=0;i<(ll)(a);++i) #define REP3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i) #define REP4(i,a,b,c) for(ll i=(ll)(a);i<(ll)(b);i+=(ll)(c)) #define rep(...) SELECT4(__VA_ARGS__,REP4,REP3,REP2,REP1)(__VA_ARGS__) #define RREP1(a) for(ll i=(ll)(a)-1;i>=0;--i) #define RREP2(i,a) for(ll i=(ll)(a)-1;i>=0;--i) #define RREP3(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i) #define rrep(...) SELECT3(__VA_ARGS__,RREP3,RREP2,RREP1)(__VA_ARGS__) #define all(v) std::begin(v),std::end(v) #define rall(v) std::rbegin(v),std::rend(v) #define INT(...) int __VA_ARGS__;scan(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;scan(__VA_ARGS__) #define STR(...) string __VA_ARGS__;scan(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;scan(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;scan(__VA_ARGS__) #define LD(...) ld __VA_ARGS__;scan(__VA_ARGS__) #define pb push_back #define eb emplace_back #line 3 "library/template/alias.hpp" using ll=long long; using ull=unsigned long long; using ld=long double; using pi=std::pair; using pl=std::pair; using vi=std::vector; using vl=std::vector; using vs=std::vector; using vc=std::vector; using vvl=std::vector; using vd=std::vector; using vp=std::vector; using vb=std::vector; template struct infinity{ static constexpr T max=std::numeric_limits::max(); static constexpr T min=std::numeric_limits::min(); static constexpr T value=std::numeric_limits::max()/2; static constexpr T mvalue=std::numeric_limits::min()/2; }; templateconstexpr T INF=infinity::value; constexpr ll inf=INF; constexpr ld EPS=1e-8; constexpr ld PI=3.1415926535897932384626; constexpr int dx[8]={1,0,-1,0,1,-1,-1,1}; constexpr int dy[8]={0,1,0,-1,1,1,-1,-1}; #line 5 "library/template/func.hpp" inline constexpr int msb(ull x){ int res=x?0:-1; if(x&0xffffffff00000000)x&=0xffffffff00000000,res+=32; if(x&0xffff0000ffff0000)x&=0xffff0000ffff0000,res+=16; if(x&0xff00ff00ff00ff00)x&=0xff00ff00ff00ff00,res+=8; if(x&0xf0f0f0f0f0f0f0f0)x&=0xf0f0f0f0f0f0f0f0,res+=4; if(x&0xcccccccccccccccc)x&=0xcccccccccccccccc,res+=2; return res+(x&0xaaaaaaaaaaaaaaaa?1:0); } inline constexpr int ceil_log2(ull x){return x?msb(x-1)+1:0;} inline constexpr ull reverse(ull x){ x=((x&0x5555555555555555)<<1)|((x&0xaaaaaaaaaaaaaaaa)>>1); x=((x&0x3333333333333333)<<2)|((x&0xcccccccccccccccc)>>2); x=((x&0x0f0f0f0f0f0f0f0f)<<4)|((x&0xf0f0f0f0f0f0f0f0)>>4); x=((x&0x00ff00ff00ff00ff)<<8)|((x&0xff00ff00ff00ff00)>>8); x=((x&0x0000ffff0000ffff)<<16)|((x&0xffff0000ffff0000)>>16); return (x<<32)|(x>>32); } inline constexpr ull reverse(ull x,int len){return reverse(x)>>(64-len);} inline constexpr int popcnt(ull x){ #if __cplusplus>=202002L return std::popcount(x); #endif x=(x&0x5555555555555555)+((x>>1)&0x5555555555555555); x=(x&0x3333333333333333)+((x>>2)&0x3333333333333333); x=(x&0x0f0f0f0f0f0f0f0f)+((x>>4)&0x0f0f0f0f0f0f0f0f); x=(x&0x00ff00ff00ff00ff)+((x>>8)&0x00ff00ff00ff00ff); x=(x&0x0000ffff0000ffff)+((x>>16)&0x0000ffff0000ffff); return (x&0x00000000ffffffff)+((x>>32)&0x00000000ffffffff); } template inline constexpr bool chmin(T&a,U b){return a>b&&(a=b,true);} template inline constexpr bool chmax(T&a,U b){return a>=1; } return res; } inline constexpr ll mod_pow(ll a,ll b,const ll&mod){ if(mod==1)return 0; a%=mod; ll res=1; while(b){ if(b&1)(res*=a)%=mod; (a*=a)%=mod; b>>=1; } return res; } inline ll mod_inv(ll a,const ll&mod){ ll b=mod,x=1,u=0,t; while(b){ t=a/b; std::swap(a-=t*b,b); std::swap(x-=t*u,u); } if(x<0)x+=mod; return x; } template std::ostream &operator<<(std::ostream&os,const std::pair&p){os< std::istream &operator>>(std::istream&is,std::pair&p){is>>p.first>>p.second;return is;} template std::ostream &operator<<(std::ostream&os,const std::vector&v){for(auto it=std::begin(v);it!=std::end(v);){os<<*it<<((++it)!=std::end(v)?" ":"");}return os;} template std::istream &operator>>(std::istream&is,std::vector&v){for(T &in:v){is>>in;}return is;} inline void scan(){} template inline void scan(Head&head,Tail&... tail){std::cin>>head;scan(tail...);} template inline void print(const T &t){std::cout< inline void print(const Head &head, const Tail &... tail){std::cout< inline void fin(const T &... a){print(a...);exit(0);} #line 5 "library/template/util.hpp" struct IOSetup{ IOSetup(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); std::cout.tie(0); std::cout< struct REC{ private: F f; public: explicit constexpr REC(F&&f_):f(std::forward(f_)){} template constexpr auto operator()(Args&&...args)const{ return f(*this, std::forward(args)...); } }; template> struct compressor{ private: std::vectordata; Comp cmp; bool sorted=false; public: compressor():compressor(Comp()){} compressor(const Comp&cmp):cmp(cmp){} compressor(const std::vector&dat,const Comp&cmp=Comp()):data(dat),cmp(cmp){} compressor(std::vector&&dat,const Comp&cmp=Comp()):data(std::move(dat)),cmp(cmp){} compressor(std::initializer_listli,const Comp&cmp=Comp()):data(li.begin(),li.end()),cmp(cmp){} void push_back(const T&v){assert(!sorted);data.push_back(v);} void push_back(T&&v){assert(!sorted);data.push_back(std::move(v));} templatevoid emplace_back(Args&&...args){assert(!sorted);data.emplace_back(std::forward(args)...);} void push(const std::vector&v){ assert(!sorted); const int n=data.size(); data.resize(v.size()+n); for(int i=0;i<(int)v.size();i++)data[i+n]=v[i]; } void build(){ assert(!sorted);sorted=1; std::sort(data.begin(),data.end(),cmp); data.erase(unique(data.begin(),data.end(),[&](const T&l,const T&r)->bool {return !cmp(l,r)&&!cmp(r,l);}),data.end()); } const T&operator[](int k)const& { assert(sorted); return data[k]; } int get_index(const T&v)const { assert(sorted); return int(lower_bound(data.begin(),data.end(),v,cmp)-data.begin()); } void press(std::vector&v)const { assert(sorted); for(auto&&i:v)i=get_index(i); } std::vectorpressed(const std::vector&v)const { assert(sorted); std::vectorret(v.size()); for(int i=0;i<(int)v.size();i++)ret[i]=get_index(v[i]); return ret; } int size()const { assert(sorted); return data.size(); } }; #line 4 "library/template/debug.hpp" template struct is_specialize:std::false_type{}; template struct is_specialize::type>:std::true_type{}; template struct is_specialize::type>:std::true_type{}; template struct is_specialize::value,void>>:std::true_type{}; inline void dump(const char&t){std::cerr<::value,std::nullptr_t> =nullptr> inline void dump(const T&t){std::cerr< inline void dump(const T&t,std::enable_if_t::value>* =nullptr){std::string tmp;if(t==infinity::value||t==infinity::max)tmp="inf";if(std::is_signed::value&&(t==infinity::mvalue||t==infinity::min))tmp="-inf";if(tmp.empty())tmp=std::to_string(t);std::cerr< inline void dump(const std::pair&); template inline void dump(const T&t,std::enable_if_t::value>* =nullptr){std::cerr<<"{";for(auto it=std::begin(t);it!=std::end(t);){dump(*it);std::cerr<<(++it==t.end()?"":",");}std::cerr<<"}";} template inline void dump(const std::pair&t){std::cerr<<"(";dump(t.first);std::cerr<<",";dump(t.second);std::cerr<<")";} inline void trace(){std::cerr< inline void trace(Head&&head,Tail&&... tail){dump(head);if(sizeof...(tail))std::cerr<<",";trace(std::forward(tail)...);} #ifdef ONLINE_JUDGE #define debug(...) (void(0)) #else #define debug(...) do{std::cerr<<#__VA_ARGS__<<"=";trace(__VA_ARGS__);}while(0) #endif #line 4 "library/template/type-traits.hpp" template struct int_least{ static_assert(size<=128,"size must be less than or equal to 128"); using type=typename std::conditional< size<=8,std::int_least8_t, typename std::conditional< size<=16,std::int_least16_t, typename std::conditional< size<=32,std::int_least32_t, typename std::conditional::type>::type>::type>::type; }; templateusing int_least_t=typename int_least::type; template struct uint_least{ static_assert(size<=128,"size must be less than or equal to 128"); using type=typename std::conditional< size<=8,std::uint_least8_t, typename std::conditional< size<=16,std::uint_least16_t, typename std::conditional< size<=32,std::uint_least32_t, typename std::conditional::type>::type>::type>::type; }; templateusing uint_least_t=typename uint_least::type; template using double_size_int=int_least::digits*2+1>; templateusing double_size_int_t=typename double_size_int::type; template using double_size_uint=uint_least::digits*2>; templateusing double_size_uint_t=typename double_size_uint::type; template using double_size=typename std::conditional::value,double_size_int,double_size_uint>::type; templateusing double_size_t=typename double_size::type; #line 9 "library/template/template.hpp" using namespace std; #line 3 "bigint.hpp" #include const int DIGIT = 6; const int BASE = 1000000; struct positive_bigint{ std::vector d; positive_bigint(){ } positive_bigint(long long X){ while (X > 0){ d.push_back(X % BASE); X /= BASE; } } positive_bigint(std::string S){ if (S == "0"){ S = ""; } int L = S.size(); d.resize((L + DIGIT - 1) / DIGIT, 0); for (int i = L - 1; i >= 0; i -= 6){ for (int j = std::max(i - 5, 0); j <= i; j++){ d[i / DIGIT] *= 10; d[i / DIGIT] += S[j] - '0'; } } std::reverse(d.begin(), d.end()); } bool empty() const { return d.empty(); } int size() const { return d.size(); } int& operator [](int i){ return d[i]; } int operator [](int i) const { return d[i]; } }; std::string to_string(const positive_bigint &A){ int N = A.size(); std::string ans; for (int i = N - 1; i >= 0; i--){ std::string tmp = std::to_string(A[i]); if (i < N - 1){ ans += std::string(DIGIT - tmp.size(), '0'); } ans += tmp; } if (ans.empty()){ ans = "0"; } return ans; } std::istream& operator >>(std::istream &is, positive_bigint &A){ std::string S; is >> S; A = positive_bigint(S); return is; } std::ostream& operator <<(std::ostream &os, positive_bigint &A){ os << to_string(A); return os; } int cmp(const positive_bigint &A, const positive_bigint &B){ int N = A.size(); int M = B.size(); if (N < M){ return -1; } else if (N > M){ return 1; } else { for (int i = N - 1; i >= 0; i--){ if (A[i] < B[i]){ return -1; } if (A[i] > B[i]){ return 1; } } return 0; } } bool operator ==(const positive_bigint &A, const positive_bigint &B){ return cmp(A, B) == 0; } bool operator !=(const positive_bigint &A, const positive_bigint &B){ return cmp(A, B) != 0; } bool operator <(const positive_bigint &A, const positive_bigint &B){ return cmp(A, B) < 0; } bool operator >(const positive_bigint &A, const positive_bigint &B){ return cmp(A, B) > 0; } bool operator <=(const positive_bigint &A, const positive_bigint &B){ return cmp(A, B) <= 0; } bool operator >=(const positive_bigint &A, const positive_bigint &B){ return cmp(A, B) >= 0; } positive_bigint& operator +=(positive_bigint &A, const positive_bigint &B){ int N = A.size(); int M = B.size(); while (N < M){ A.d.push_back(0); N++; } for (int i = 0; i < M; i++){ A[i] += B[i]; } for (int i = 0; i < N - 1; i++){ if (A[i] >= BASE){ A[i] -= BASE; A[i + 1]++; } } if (N > 0){ if (A[N - 1] >= BASE){ A.d.push_back(1); A[N - 1] -= BASE; } } return A; } positive_bigint operator +(const positive_bigint &A, const positive_bigint &B){ positive_bigint A2 = A; A2 += B; return A2; } positive_bigint& operator -=(positive_bigint &A, const positive_bigint &B){ int N = A.size(); int M = B.size(); for (int i = 0; i < M; i++){ A[i] -= B[i]; } for (int i = 0; i < N - 1; i++){ if (A[i] < 0){ A[i] += BASE; A[i + 1]--; } } while (!A.empty()){ if (A.d.back() == 0){ A.d.pop_back(); } else { break; } } return A; } positive_bigint operator -(const positive_bigint &A, const positive_bigint &B){ positive_bigint A2 = A; A2 -= B; return A2; } positive_bigint operator *(const positive_bigint &A, const positive_bigint &B){ if (A.empty() || B.empty()){ return 0; } int N = A.size(); int M = B.size(); std::vector a(N); for (int i= 0; i < N; i++){ a[i] = A[i]; } std::vector b(M); for (int i = 0; i < M; i++){ b[i] = B[i]; } std::vector C = atcoder::convolution_ll(a, b); for (int i = 0; i < N + M - 2; i++){ C[i + 1] += C[i] / BASE; C[i] %= BASE; } if (C[N + M - 2] >= BASE){ C.resize(N + M); C[N + M - 1] += C[N + M - 2] / BASE; C[N + M - 2] %= BASE; } positive_bigint ans; ans.d.resize(C.size()); for (int i = 0; i < C.size(); i++){ ans[i] = C[i]; } return ans; } positive_bigint operator *=(positive_bigint &A, const positive_bigint &B){ A = A * B; return A; } struct bigint{ bool neg = false; positive_bigint a; bigint(){ } bigint(long long X): neg(X < 0), a(abs(X)){ } bigint(const positive_bigint &X, bool neg = false): neg(neg), a(X){ } bigint(const std::string &s){ if (!s.empty()){ if (s[0] == '-'){ neg = true; a = positive_bigint(s.substr(1, s.size() - 1)); } else { a = positive_bigint(s); } } } bool empty() const { return a.empty(); } int size() const { return a.size(); } int& operator [](int i){ return a[i]; } }; std::string to_string(const bigint &A){ std::string ans; if (A.neg){ ans += '-'; } ans += to_string(A.a); return ans; } std::istream& operator >>(std::istream &is, bigint &A){ std::string S; is >> S; if (S != "0"){ A = bigint(S); } return is; } std::ostream& operator <<(std::ostream &os, bigint A){ os << to_string(A); return os; } positive_bigint abs(const bigint &A){ return A.a; } int cmp(const bigint &A, const bigint &B){ if (!A.neg){ if (!B.neg){ return cmp(A.a, B.a); } else { return 1; } } else { if (!B.neg){ return -1; } else { return cmp(B.a, A.a); } } } bool operator ==(const bigint &A, const bigint &B){ return cmp(A, B) == 0; } bool operator !=(const bigint &A, const bigint &B){ return cmp(A, B) != 0; } bool operator <(const bigint &A, const bigint &B){ return cmp(A, B) < 0; } bool operator >(const bigint &A, const bigint &B){ return cmp(A, B) > 0; } bool operator <=(const bigint &A, const bigint &B){ return cmp(A, B) <= 0; } bool operator >=(const bigint &A, const bigint &B){ return cmp(A, B) >= 0; } bigint operator +(const bigint &A){ return A; } bigint operator -(const bigint &A){ bigint A2 = A; if (!A2.empty()){ A2.neg = !A2.neg; } return A2; } bigint& operator +=(bigint &A, const bigint &B){ if (A.neg == B.neg){ A.a += B.a; } else { int c = cmp(A.a, B.a); if (c > 0){ A.a -= B.a; } else if (c < 0){ A.a = B.a - A.a; A.neg = !A.neg; } else { A = 0; } } return A; } bigint operator +(const bigint &A, const bigint &B){ bigint A2 = A; A2 += B; return A2; } bigint& operator -=(bigint &A, const bigint &B){ if (A.neg != B.neg){ A.a += B.a; } else { int c = cmp(A.a, B.a); if (c > 0){ A.a -= B.a; } else if (c < 0){ A.a = B.a - A.a; A.neg = !A.neg; } else { A = 0; } } return A; } bigint operator -(const bigint &A, const bigint &B){ bigint A2 = A; A2 -= B; return A2; } bigint operator *=(bigint &A, const bigint &B){ if (A.empty() || B.empty()){ A = 0; } else { if (B.neg){ A.neg = !A.neg; } A.a *= B.a; } return A; } bigint operator *(const bigint &A, const bigint &B){ bigint A2 = A; A2 *= B; return A2; } #line 6 "code.cpp" typedef string::const_iterator State; bigint expression(State&st); bigint term(State&st); bigint factor(State&st); bigint number(State&st); bigint expression(State&st){ vectorf={term(st)}; while(*st=='+'||*st=='-'){ if(*st=='+'){ st++; f.pb(term(st)); }else{ st++; f.pb(-term(st)); } } if(f.size()==1)return f[0]; priority_queue,vector>,greater>>pq; rep(i,f.size()){ pq.emplace(f[i].a.size(),i); } while(pq.size()>1){ auto a=pq.top();pq.pop(); auto b=pq.top();pq.pop(); f[a.second]+=f[b.second]; pq.emplace(f[a.second].a.size(),a.second); } return f[pq.top().second]; } bigint term(State&st){ vectorf={factor(st)}; while(*st=='*'){ st++; f.emplace_back(factor(st)); } if(f.size()==1)return f[0]; priority_queue,vector>,greater>>pq; rep(i,f.size()){ pq.emplace(f[i].a.size(),i); } while(pq.size()>1){ auto a=pq.top();pq.pop(); auto b=pq.top();pq.pop(); f[a.second]*=f[b.second]; pq.emplace(f[a.second].a.size(),a.second); } return f[pq.top().second]; } bigint factor(State&st){ if(*st=='('){ st++; bigint tmp=expression(st); assert(*st==')'); st++; return tmp; } return number(st); } bigint number(State&st){ if(*st=='-'){ st++; return -number(st); } string t=""; while(isdigit(*st)){ t+=*st; st++; } return bigint(t); } int main(){ IOSetup(); LL(n); STR(s); State it=s.begin(); bigint ans=expression(it); cout<