Ta biến đổi xâu dãy ngoặc ~s_1, s_2, \ldots, s_n~ thành một mảng ~a_1, a_2, \ldots, a_n~ với quy ước: '('~ = 1~, và ')'~ = -1~. Điều kiện để xâu ~s_l, s_l + 1, \ldots, s_r~ là một dãy ngoặc đúng là:

• ~\sum_{i = l}^{t} a_i \ge 0~, ~(l \le t \le r)~.

• ~\sum_{i}^{r} a_i = 0~. (Độc giả tự chứng minh).

Subtask 1 ~(n, q \le 1000)~:

• Với mỗi truy vấn ta duyệt từ vị trí ~x~ kiểm tra có thõa là dãy ngoặc đúng hay không và cập nhập độ dài dài nhất trong ~O(n)~.

• ĐPT: ~O(n * q)~.

Subtask 2 ~(n, q \le 10^5)~:

• Dựng cây phân đoạn với nút quản lý đoạn ~[l, r]~ lưu giá trị nhỏ nhất của ~ps_i~ ~(l \le i \le r)~. Với ~ps_i = a_1 + a_2 + \ldots + a_i~.

• Với thao tác đảo dấu ngoặc ở vị trí ~x~, ta thấy rằng nó sẽ ảnh hưởng tới những vị trí từ ~x~ tới ~n~. Ta cập nhập trên đoạn các vị trí thay đổi này.

• Với thao tác tìm dãy ngoặc đúng dài nhất bắt đầu từ vị trí ~x~:

  • Chặt nhị phân tìm kiếm vị trí ~r~ xa nhất sao cho ~min(ps_x, ps_{x + 1}, \ldots, ps_{r}) - ps_{x - 1} \ge 0~.
  • Chặt nhị phân tìm kiếm vị trí ~l~ xa nhất sao cho ~min(ps_l, ps_{l + 1}, \ldots, ps_{r}) - ps_{x - 1} \le 0~.
  • Như vậy đán án bài toán là ~l - x + 1~ nếu tìm được ~l, r~ thõa mãn.
  • Ta chặt nhị phân mất ~\log\ n~, và trong mỗi lần chặt ta mất ~\log\ n~ để ~min~ trên đoạn. Do đó ta mất ~\log^2\ n~ để thực hiện thao tác tìm kiếm.

• ĐPT: ~O(q * \log^2\ n)~.

Subtask 3 ~(n, q \le 5 * 10^5)~:

• Tương tự như subtask ~2~, tuy nhiên ở thao tác tìm dãy ngoặc đúng dài nhất ta sẽ sử dụng Walk on Segment tree nhờ đó giảm độ phức tạp xuống ~log\ n~ cho mỗi lần tìm kiếm.

• ĐPT: ~O(q * log\ n)~.

/*
Tag: 
*/
#include <bits/stdc++.h>
#define ll long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;
const int oo = 1e9;

class SegmentTree{

private:
    int n;
    vector<int> seg;
    vector<int> pref, lazy;


    void build(int id, int l, int r){
        if (l == r){
            seg[id] = pref[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);

        seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
    }

    void push(int id, int l, int r){
        int &t = lazy[id];
        if (t == 0) return;

        seg[id << 1] += t;
        seg[id << 1 | 1] += t;

        lazy[id << 1] += t;
        lazy[id << 1 | 1] += t;

        t = 0;
    }

    void update(int id, int l, int r, int ls, int rs, int val){
        if (ls > r || l > rs) return;
        if (ls <= l && r <= rs){
            seg[id] += val;
            lazy[id] += val;
            return;
        }
        push(id, l, r);

        int mid = (l + r) >> 1;
        update(id << 1, l, mid, ls, rs, val);
        update(id << 1 | 1, mid + 1, r, ls, rs, val);

        seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
    }

    int get(int id, int l, int r, int ls, int rs){
        if (l > rs || ls > r) return oo;
        if (ls <= l && r <= rs) return seg[id];
        int mid = (l + r) >> 1;
        push(id, l, r);

        return min(get(id << 1, l, mid, ls, rs), get(id << 1 | 1, mid + 1, r, ls, rs));
    }

    int upper(int id, int l, int r, int ls, int rs, int upperVal){
        if (seg[id] >= upperVal) return oo;
        if (ls > r || l > rs) return oo;
        if (l == r) return l;

        push(id, l, r);
        int mid = (l + r) >> 1;
        int res = oo;
        // cout << l << " " << r << " " << seg[id << 1] << " " << seg[id << 1 | 1] << endl;
        if (seg[id << 1] < upperVal){
            res = upper(id << 1, l, mid, ls, rs, upperVal);
        }

        if (res == oo){
            res = upper(id << 1 | 1, mid + 1, r, ls, rs, upperVal);
        }

        return res;

    }

    int lower(int id, int l, int r, int ls, int rs, int lowerVal){
        if (ls > r || l > rs) return oo;
        if (seg[id] > lowerVal) return oo;
        if (l == r) return l;
        push(id, l, r);

        int mid = (l + r) >> 1;
        int res = oo;
        if (seg[id << 1 | 1] <= lowerVal){
            res = lower(id << 1 | 1, mid + 1, r, ls, rs, lowerVal);
        }

        if (res == oo){
            res = lower(id << 1, l, mid, ls, rs, lowerVal);
        }
        return res;
    }

public:
    SegmentTree(int _n, vector<int> &_pref): n(_n), pref(_pref), seg(4 * _n + 10), lazy(4 * _n + 10) {}

    void build(){
        build(1, 0, n);
    }

    void update(int l, int r, int delta){
        update(1, 0, n, l, r, delta);
    }

    int get(int l, int r){
        return get(1, 0, n, l, r);
    }

    int upper(int l, int r, int val){
        return upper(1, 0, n, l, r, val);
    }

    int lower(int l, int r, int val){
        return lower(1, 0, n, l, r, val);
    }
};

const int MAXN = 1e6 + 5;

int n, q;
string s;
vector<int> pref;

void prep(){
    pref.resize(n + 1);
    for (int i = 1; i <= n; i++){
        pref[i] = pref[i - 1] + ((s[i] == '(') ? 1 : -1);
    }
}

void PROGRAM(int _){
    cin >> n >> q >> s;

    s = '+' + s;

    prep();

    SegmentTree d(n, pref);
    d.build();

    while (q--){
        int type, x;
        cin >> type >> x;
        if (type == 1){
            if (s[x] == '('){
                d.update(x, n, -2);
                s[x] = ')';
            } else{
                d.update(x, n, 2);
                s[x] = '(';
            }

        } else{
            int valOfX = d.get(x - 1, x - 1);
            int upper = d.upper(x, n, valOfX);
            if (upper == oo) upper = n;
            else upper--;
            int lower = d.lower(x, upper, valOfX);
            if (lower == oo) cout << 0 << endl;
            else cout << lower - x + 1 << endl;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;

    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}