只需要管没有修改有括号那个 sub，解法我在上一个帖子里面已经发过了（雾）。

然后我还是 WA……wtcl，貌似大部分都错在没判出 $-1$？

代码：

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <algorithm>
#include <cstdlib>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
	register char c = getchar();
	register int x = 0, f = 1;
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + c - 48;
		c = getchar();
	}
	return x * f;
}

inline int Abs(const int& x) {return (x > 0 ? x : -x);}
inline int Max(const int& x, const int& y) {return (x > y ? x : y);}
inline int Min(const int& x, const int& y) {return (x < y ? x : y);}

const long long mod = 1000000007;
long long pow10[300005];
char s1[100005], s[300005];
int n, m, presum[300005], d;

// RMQ

struct Segtree {
	int val[1200005];
	inline void Modify(int p, int pl, int pr, int idx, int v) {
		if (pl == idx && pr == idx) {
			val[p] = v;
			return;
		}
		register int mid = pl + pr >> 1;
		if (mid >= idx) Modify(p << 1, pl, mid, idx, v);
		else Modify(p << 1 | 1, mid + 1, pr, idx, v);
		val[p] = Min(val[p << 1], val[p << 1 | 1]);
	}
	inline int Query(int p, int pl, int pr, int l, int r) {
		if (pl == l && pr == r) return val[p];
		register int mid = pl + pr >> 1;
		if (mid >= r) return Query(p << 1, pl, mid, l, r);
		else if (mid + 1 <= l) return Query(p << 1 | 1, mid + 1, pr, l, r);
		else return Min(Query(p << 1, pl, mid, l, mid), Query(p << 1 | 1, mid + 1, pr, mid + 1, r));
	}
};
Segtree sgt;

// Treap

#define GetSize(p) (p ? p->siz : 0)
#define GetVal(p) (p ? p->val : 0)
#define GetRevval(p) (p ? p->revval : 0)
struct Node {
	char c;
	int pri, rnd, siz;
	long long val, revval;
	Node *l, *r, *mid, *fa;
	inline void Update() {
		if (c >= '0' && c <= '9') {
			if ((l && l->c == '(') || (r && r->c == '(') || (l && l->val == -1) || (r && r->val == -1)) val = revval = -1;
			else revval = val = (((long long)(c - 48) * pow10[GetSize(r)] % mod + GetVal(r)) % mod + GetVal(l) * pow10[GetSize(r) + 1] % mod) % mod;
		} else if (c == '+') {
			if (!l || !r || GetVal(l) == -1 || GetVal(r) == -1) revval = val = -1;
			else {
				val = (GetVal(l) + GetVal(r)) % mod;
				revval = ((GetRevval(l) - GetVal(r)) % mod + mod) % mod;
			}
		} else if (c == '-') {
			if (!l || !r || GetVal(l) == -1 || GetVal(r) == -1) revval = val = -1;
			else {
				val = ((GetVal(l) - GetRevval(r)) % mod + mod) % mod;
				revval = (GetRevval(l) + GetRevval(r)) % mod;
			}
		} else if (c == '*') {
			if (!l || !r || GetVal(l) == -1 || GetVal(r) == -1) val = revval = -1;
			else val = revval = (GetVal(l) * GetVal(r)) % mod;
		} else {
			if (l || r) val = revval = -1;
			else if (!mid) val = revval = -1;
			else val = revval = mid->val;
		}
		siz = GetSize(l) + GetSize(r) + GetSize(mid);
		if (c == '(') siz += 2;
		else siz += 1;
		if (l) l->fa = this;
		if (r) r->fa = this;
		if (mid) mid->fa = this;
	}
};
Node nd[600005];
int top = 0;
struct Fhqtreap {
	Node *_root;
	inline Node* New(char c) {
		Node *p = &nd[top++];
		if (c >= '0' && c <= '9') p->pri = 4;
		else if (c == '(') p->pri = 3;
		else if (c == '*') p->pri = 2;
		else p->pri = 1;
		p->rnd = rand();
		p->c = c;
		p->l = p->r = p->mid = p->fa = NULL;
		p->Update();
		return p;
	}
	inline void split(Node *now, int siz, Node *&lt, Node *&rt) {
		if (!now) {
			lt = rt = NULL;
			return;
		}
		if (GetSize(now->l) < siz) {
			lt = now;
			split(now->r, siz - GetSize(now->l) - GetSize(now->mid) - (now->c == '(' ? 2 : 1), now->r, rt);
		} else {
			rt = now;
			split(now->l, siz, lt, now->l);
		}
		now->Update();
	}
	inline Node* merge(Node *lt, Node *rt) {
		if (!lt) return rt;
		if (!rt) return lt;
		if (lt->pri < rt->pri || (lt->pri == rt->pri && lt->rnd < rt->rnd)) {
			lt->r = merge(lt->r, rt);
			lt->Update();
			return lt;
		} else {
			rt->l = merge(lt, rt->l);
			rt->Update();
			return rt;
		}
	}
	inline Node* Fetch(Node *p, int siz) {
		if (p->c != '(') {
			if (siz < GetSize(p->l)) return Fetch(p->l, siz);
			else if (siz == GetSize(p->l)) return p;
			else return Fetch(p->r, siz - GetSize(p->l) - 1);
		} else {
			if (siz < GetSize(p->l)) return Fetch(p->l, siz);
			else if (siz == GetSize(p->l)) return p;
			else if (siz < GetSize(p->l) + 1 + GetSize(p->mid)) return Fetch(p->mid, siz - GetSize(p->l) - 1);
			else if (siz == GetSize(p->l) + 1 + GetSize(p->mid)) return p;
			else return Fetch(p->r, siz - GetSize(p->l) - GetSize(p->mid) - 2);
		}
	}
	inline Node* Belong(Node *p) {
		while (!(p->fa->c == '(' && p->fa->mid == p)) p = p->fa;
		p = p->fa;
		return p;
	}
	inline void Dfs(Node *p) {
		if (!p) return;
		if (p->c != '(') {
			Dfs(p->l);
			putchar(p->c);
			Dfs(p->r);
		} else {
			Dfs(p->l);
			putchar('(');
			Dfs(p->mid);
			putchar(')');
			Dfs(p->r);
		}
	}
};
Fhqtreap tr;

inline void Init() {
	pow10[0] = 1;
	for (register int i = 1;i <= 300000;i++) pow10[i] = pow10[i - 1] * 10ll % mod;
}

inline void Read() {
	scanf("%d%d", &n, &m);
	scanf("%s", s1 + 1);
}

inline void Prefix() {
	register int cur = 0;
	for (register int i = 1;i <= n;i++) {
		if (s1[i] == '(') cur++;
		if (s1[i] == ')') cur--;
		d = Min(d, cur);
	}
	d = -d;
	for (register int i = 1;i <= d + 1;i++) s[i] = '(';
	for (register int i = 1;i <= n;i++) s[i + d + 1] = s1[i];
	cur += d;
	for (register int i = 1;i <= cur + 1;i++) s[n + d + i + 1] = ')';
	n = n + d + cur + 2;
	//for (register int i = 1;i <= n;i++) putchar(s[i]);
	//putchar('\n');
	for (register int i = 1;i <= n;i++){
		presum[i] = presum[i - 1];
		if (s[i] == '(') presum[i]++;
		if (s[i] == ')') presum[i]--;
		sgt.Modify(1, 1, n, i, presum[i]);
	}
}

inline Node* Buildtree(int &i) {
	i++;
	Node *res = NULL;
	while (i <= n && s[i] != ')') {
		//printf("i=%d\n", i);
		if (s[i] == '(') {
			Node *cur = tr.New('(');
			cur->mid = Buildtree(i);
			cur->Update();
			res = tr.merge(res, cur);
		} else {
			res = tr.merge(res, tr.New(s[i]));
		}
		i++;
	}
	return res;
}

inline int Direction(Node *p) {
	if (!(p->fa)) return -1;
	if (p->fa->l == p) return 0;
	if (p->fa->mid == p) return 1;
	if (p->fa->r == p) return 2;
}

inline int queryRank(Node *p) {
	register int ans = 0;
	for (;;) {
		register int cur = Direction(p);
		if (cur == -1) break;
		else if (cur == 2) ans += GetSize(p->fa->l) + GetSize(p->fa->mid) + (p->fa->c == '(' ? 2 : 1);
		else if (cur == 1) ans += GetSize(p->fa->l) + 1;
		p = p->fa;
	}
	return ans;
}

inline void Solve() {
	while (m--) {
		register int opt;
		scanf("%d", &opt);
		if (opt == 2) {
			register int l, r;
			scanf("%d%d", &l, &r);
			l += d + 1; r += d + 1;
			if (presum[r] != presum[l - 1] || sgt.Query(1, 1, n, l, r) < presum[r]) {
				puts("-1");
				continue;
			}
			//printf("%c\n", (tr.Fetch(tr._root, l - 1))->c);
			Node *pl = tr.Belong(tr.Fetch(tr._root, l - 1));
			//printf("pl:%c\n", pl->c);
			//tr.Dfs(pl);
			//putchar('\n');
			register int siz = queryRank(pl);
			//printf("siz=%d\n", siz);
			Node *p1, *p2, *p3;
			tr.split(pl->mid, l - siz - 2, p1, p2);
			tr.split(p2, r - l + 1, p2, p3);
			//tr.Dfs(p2);
			//putchar('\n');
			if (p2) printf("%lld\n", p2->val);
			else puts("-1");
			pl->mid = tr.merge(tr.merge(p1, p2), p3);
		} else {
            register int idx;
            register char opt;
            scanf("%d %c", &idx, &opt);
            Node *p1, *p2, *p3;
            tr.split(tr._root->mid, idx - 1, p1, p2);
            tr.split(p2, 1, p2, p3);
            p2 = tr.New(opt);
            p2->Update();
            tr._root->mid = tr.merge(tr.merge(p1, p2), p3);
            tr._root->Update();
        }
	}
}

int main() {
	//srand(unsigned(time(NULL)));
	Init();
	Read();
	Prefix();
	register int i = 0;
	tr._root = Buildtree(i);
	//tr.Dfs(tr._root);
	//putchar('\n');
	Solve();
	#ifndef ONLINE_JUDGE
	while (1);
	#endif
	return 0;
}