#include #include #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; } #if 0 __END__ #endif #include #define fr(i,n) for(int i=0;i<(n);++i) #define foor(i,a,b) for(int i=(a);i<=(b);++i) #define rf(i,n) for(int i=(n);i-->0;) #define roof(i,b,a) for(int i=(b);i>=(a);--i) #define elsif else if #define all(x) x.begin(),x.end() #define Sort(x) sort(all(x)) #define Reverse(x) reverse(all(x)) #define Rev(x) reverse(all(x)) #define Uniq(v) v.erase(unique(all(v)),v.end()) #define PQ priority_queue #define NP(x) next_permutation(all(x)) #define M_PI 3.14159265358979323846 #define popcount __builtin_popcountll using namespace std; using vb=vector;using vvb=vector; using vi=vector;using vvi=vector;using vvvi=vector; using ll=long long; using vl=vector< ll>;using vvl=vector;using vvvl=vector; using ull=unsigned long long;using vu=vector;using vvu=vector; using dbl=double; using vd=vector;using vvd=vector;using vvvd=vector; using str=string; using vs=vector;using vvs=vector; using pii=pair; using vpii=vector;using mii=map; using pll=pair< ll, ll>; using vpll=vector;using mll=map< ll, ll>; using pdd=pair; using vpdd=vector;using mdd=map; using pss=pair; using vpss=vector;using mss=map; using pil=pair; using vpil=vector;using mil=map; using pli=pair< ll,int>; using vpli=vector;using mli=map< ll,int>; using pdi=pair; using vpdi=vector;using mdi=map; templatevector&operator<<(vector&v,const T t){v.push_back(t);return v;} templatemultiset&operator<<(multiset&m,const T t){m.insert(t);return m;} templateset&operator<<(set&s,const T t){s.insert(t);return s;} templatestack&operator<<(stack&s,const T t){s.push(t);return s;} templatestack&operator>>(stack&s,T&t){t=s.top();s.pop();return s;} templatequeue&operator<<(queue&q,const T t){q.push(t);return q;} templatequeue&operator>>(queue&q,T&t){t=q.front();q.pop();return q;} templatePQ,U>&operator<<(PQ,U>&q,const T t){q.push(t);return q;} templatePQ,U>&operator>>(PQ,U>&q,T&t){t=q.top();q.pop();return q;} templateistream&operator>>(istream&s,pair&p){return s>>p.first>>p.second;} istream&operator>>(istream&s,_Bit_reference b){int a;s>>a;assert(a==0||a==1);b=a;return s;} templateistream&operator>>(istream&s,vector&v){fr(i,v.size()){s>>v[i];}return s;} templateostream&operator<<(ostream&s,const pairp){return s<ostream&operator<<(ostream&s,const vectorv){fr(i,v.size()){i?s<<" "<ostream&operator<<(ostream&s,const dequed){fr(i,d.size()){i?s<<" "<_Bit_reference operator&=(_Bit_reference b,T t){return b=b&t;} template_Bit_reference operator^=(_Bit_reference b,T t){return b=b^t;} template_Bit_reference operator|=(_Bit_reference b,T t){return b=b|t;} templatepairoperator+(paira,pairb){return {a.first+b.first,a.second+b.second};} templatepairoperator-(paira,pairb){return {a.first-b.first,a.second-b.second};} templatepair&operator+=(pair&a,pairb){return a=a+b;} templatepair&operator-=(pair&a,pairb){return a=a-b;} void print(void){cout<<"\n";} void Print(void){cout<void print(T t){cout<void Print(T t){cout<void print(T&&t,U&&...u){cout<(u)...);} templatevoid Print(T&&t,U&&...u){cout<(u)...);} bool YN(bool b){print(b?"YES":"NO");return b;}bool PI(bool b){print(b?"POSSIBLE":"IMPOSSIBLE");return b;} bool Yn(bool b){print(b?"Yes":"No");return b;}bool Pi(bool b){print(b?"Possible":"Impossible");return b;} bool yn(bool b){print(b?"yes":"no");return b;}bool pi(bool b){print(b?"possible":"impossible");return b;} const int e5=1e5; const int e9=1e9; const int MD=1e9+7; const int md=998244353; const ll e18=1e18; templatestr to_string(const T&n){ostringstream s;s<bool chmax(T&a,T b){return abool chmin(T&a,T b){return a>b?(a=b,true):false;} templatevector>dijkstra(const vector>>&E,const U s,const T inf){using P=pair;vector

d;fr(i,E.size()){d<,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.firstmap>dijkstra(map>>E,const U s,const T inf){using P=pair;mapd;for(pair>e:E){d[e.first]=P{inf,e.first};}PQ,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.first&E,int s,int t){ll z=0;vi b(E.size(),-1);for(int i=0;;++i){static auto dfs=[&](int v,ll f,auto&dfs)->ll{if(v==t)return f;b[v]=i;for(auto&p:E[v]){if(b[p.first]T distsq(paira,pairb){return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);} templateT max(const vectora){assert(a.size());T m=a[0];for(T e:a){m=max(m,e);}return m;} templateT min(const vectora){assert(a.size());T m=a[0];for(T e:a){m=min(m,e);}return m;} templateT gcd(const T a,const T b){return a?gcd(b%a,a):b;} templateT gcd(const vectora){T g=a[0];for(T e:a){g=gcd(g,e);}return g;} //templatevectorLCS(vectorA,vectorB){int N=A.size(),M=B.size();vector>>d(N+1,vector>(M+1));fr(i,N){fr(j,M){if(A[i]==B[j]){d[i+1][j+1]={d[i][j].first+1,{i,j}};}else{d[i+1][j+1]=max(d[i][j+1],d[i+1][j]);}}}vectorr;for(pii p={N,M};d[p.first][p.second].first;p=d[p.first][p.second].second){r<s=LCS(vector(S.begin(),S.end()),vector(T.begin(),T.end()));return str(s.begin(),s.end());} //templatevector>ConvexHull(vector>V){if(V.size()<=3){return V;}Sort(V);rf(i,V.size()-1)V<>r;for(pairp:V){int s=r.size();while(s>=2&&(p.second-r[s-1].second)*(p.first-r[s-2].first)<(p.second-r[s-2].second)*(p.first-r[s-1].first)){r.pop_back();--s;}r<s[b]){swap(a,b);}s[b]+=s[a];p[a]=b;}}void unite(pii p){return unite(p.first,p.second);}bool same(int a,int b){extend(a);extend(b);return find(a)==find(b);}bool same(pii p){return same(p.first,p.second);}int size(int x){extend(x);return s[find(x)];}}; //ll MST(vector>&E){Sort(E);UnionFind uf;ll z=0;for(auto&e:E){if(!uf.same(e.second)){z+=e.first;uf.unite(e.second);}}return z;} //ll strmod(const str&s,const int m){ll x=0;fr(i,s.size()){x=(x*10+s[i]-48)%m;}return x;} vvl mul(const vvl&A,const vvl&B,const int m){vvl C;fr(y,A.size()){C<=0?a%m:(m-(-a%m))%m:1)*(t=pow(a,n>>1,m),t*t%m)%m:1;} ll inv(const ll x,const int p){assert(x!=0);return pow(x,p-2,p);} //ll inv(const ll x){return inv(x,MD);} vpll fact(const int n,const int p){assert(nint MSB(T N){int r=-1;for(;N>0;N/=2){++r;}return r;} templateclass SegmentTree{vectorS;T(*const op)(T a,T b);const T zero;const int B;public:SegmentTree(int N,T(*f)(T a,T b),const T zero):S(1<v,T(*f)(T a,T b),const T zero):SegmentTree(v.size(),f,zero){fr(i,v.size()){S[S.size()/2+i]=v[i];}roof(i,S.size()/2-1,1){S[i]=op(S[i*2],S[i*2+1]);}}T calc(int l,int r){l+=B;r+=B;if(l>r){return zero;}if(l==r){return S[l];}T L=S[l],R=S[r];for(;l/20){z+=B[i];i-=i&-i;}return z;} //void BITadd(vl&B,int i,ll x){while(i>i&1){a=A;b=B;c=C;d=D;A=a+b;B=a;C=c+d;D=c;}a=A%m;b=B%m;c=C%m;d=D%m;}return b;} vi primes(int n){vb b(n+1);vi p;foor(i,2,n){if(!b[i]){p<=max(L,i+i);j-=i){B[j-L]=false;}}}vl P;for(ll i=max(2ll,L);i<=R;++i){if(B[i-L]){P<dfs=[&](int i,int p){for(int j:E[i])if(j!=p){par[0][j]=i;dep[j]=dep[i]+1;dfs(j,i);}};par[0][root]=root;dfs(root,root);fr(i,par.size()-1){fr(j,par[0].size()){par[i+1][j]=par[i][par[i][j]];}}}int operator()(int a,int b){if(dep[a]>dep[b])swap(a,b);for(int t=dep[b]-dep[a],i=0;t;t>>=1,++i){if(t&1){b=par[i][b];}}if(a==b)return a;rf(i,par.size()){if(par[i][a]!=par[i][b]){a=par[i][a];b=par[i][b];}}return par[0][a];}int dist(int a,int b){return dep[a]+dep[b]-2*dep[operator()(a,b)];}}; vpli factor(ll N){vpli r;for(ll i=2;i*i<=N;++i){if(N%i==0){r<1){r<bool{if(rank[a]!=rank[b])return rank[a]void sort2(vector&a,vector&b){int N=a.size();assert(b.size()==N);vector>v;fr(i,N){v<{a[i],b[i]};}Sort(v);fr(i,N){a[i]=v[i].first;b[i]=v[i].second;}} templatevoid sort3(vector&a,vector&b,vector&c){int N=a.size();assert(b.size()==N);assert(c.size()==N);vector>>v;fr(i,N){v.push_back({a[i],{b[i],c[i]}});}Sort(v);fr(i,N){a[i]=v[i].first;b[i]=v[i].second.first;c[i]=v[i].second.second;}} vi toposo(vvi E){int N=E.size();vi T(N,-1);{vvi R(N);vi v;{vb u(N);functionf=[&](int i){if(u[i])return;u[i]=true;for(int j:E[i]){R[j]<f=[&](int i){T[i]=k;for(int j:R[i]){if(T[j]==-1){f(j);}}};rf(i,v.size()){if(T[v[i]]==-1){f(v[i]);++k;}}}}return T;} vb SAT2(vvi E){int N=E.size();assert(N%2==0);vi T=toposo(E);vb z(N);fr(i,N/2){if(T[2*i]==T[2*i+1]){return vb{};}z[2*i+(T[2*i]a2){swap(a1,a2);swap(m1,m2);}return INV(m1,m2)*(a2-a1)%m2*m1+a1;} //ull mulull(ull a,ull b,ull m){using ld=long double;ll t=a*b-m*ull(ld(a)*ld(b)/ld(m));return t+m*(t<0)-m*(t>=ll(m));} //ll powll(const ll a,const ll n,const ll m){return n?n%2?mulull(a,powll(a,n-1,m),m):powll(mulull(a,a,m),n/2,m):1;} //bool MillerRabin(int n){if(n<2){return false;}int d=n-1,s=0;for(;d%2==0;d/=2){++s;}if(s==0){return n==2;}for(int a:{2,7,61})if(a=2&&mf[x]==x;}int minfactor(int x){assert(x>=2);assert(x=1);assert(x1){if(v.empty()||v.back().first=1);assert(x1;--m){if(pow(t,1<q;q<>i;for(int j:E[i]){if(d[j]<0){d[j]=d[i]+1;q<vectorslidemax(const vector&v,int k){assert(1<=k&&k<=int(v.size()));--k;vectord(v.size()-k);dequeq;fr(j,k){while(q.size()&&v[q.back()]<=v[j]){q.pop_back();}q.push_back(j);}fr(j,v.size()-k){while(q.size()&&v[q.back()]<=v[j+k]){q.pop_back();}q.push_back(j+k);d[j]=v[q.front()];if(q.front()==j){q.pop_front();}}return d;} int main(){cin.tie(0);ios::sync_with_stdio(false); int N;cin>>N; str S;cin>>S; S="(("s+S+")"s; N=S.size(); vector>v; fr(i,N){ char c=S[i]; char l=i-1>=0?S[i-1]:'('; char r=i+1=2); v[v.size()-2].second*=v.back().first+v.back().second; v.pop_back(); if(r=='+'||r=='-'){ v.back().first+=v.back().second; v.back().second=1; } }elsif(c=='-'){ v.back().second*=-1; }elsif('0'<=c&&c<='9'){ if('0'<=l&&l<='9'){ v.back().second*=10; v.back().second+=c-'0'; }else{ v.emplace_back(0,c-'0'); } if(!('0'<=r&&r<='9')){ assert(v.size()>=2); assert(v.back().first==0); v[v.size()-2].second*=v.back().second; v.pop_back(); } if(r=='+'||r=='-'){ v.back().first+=v.back().second; v.back().second=1; } } } assert(v.size()==1); print(v[0].second); return 0; } #if 0 #endif