#include <bits/stdc++.h> using namespace std; #define ll long long int #define ull unsigned long long int #define ul unsigned long #define ld long double #define pb push_back #define eb emplace_back #define mp make_pair #define mt make_tuple #define fi first #define se second #define FORUP(i, star, end) for (int i = star; i <= end; ++i) #define FORDOWN(i, star, end) for (int i = end; i >= star; --i) #define FORAUTO(item, m) for (auto item : m) #define foreach(vector) \ for (auto it : vector) cout << it << ' '; #define Map_Foreach(map) \ for (auto it : map) cout << it.fi << ' ' << it.se << "\n"; #define REP(i, n) for (int i = 0; i < n; ++i) #define REV(i, n) for (int i = n - 1; i >= 0; --i) #define AutoInputArray(a, b, x) FORUP(a, 1, b) cin >> x[i]; #define AutoInputArrayFr0(a, b, x) REP(0, n) cin >> x[i]; #define whatis(x) cout << "Line " << __LINE__ << ": " << #x << " = " << (x) << ", "; #define ShowTime() cerr << "Executed in " << clock() * 1000 / CLOCKS_PER_SEC << " ms"; #define UpCase(s) transform(s.begin(), s.end(), s.begin(), ::toupper); #define LowCase(s) transform(s.begin(), s.end(), s.begin(), ::tolower); #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define len(x) (int)x.size() #define endl "\n" void debug_out() { cerr << endl; } void in() {} void out() {} // inline int getchar_unlocked() { return _getchar_nolock(); } // inline int putchar_unlocked(char c) { return _putchar_nolock(c); } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H << ","; debug_out(T...); } template <typename A, typename B> ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << p.first << " " << p.second; } template <typename a, typename b, typename c> ostream &operator<<(ostream &os, const pair<a, pair<b, c>> &p) { return os << p.second.first << ' ' << p.second.second; } template <typename T> void inp(T &x) { x = 0; bool neg = 0; T c = getchar_unlocked(); if (c == '-') neg = 1, c = getchar_unlocked(); while ((c < 48) || (c > 57)) c = getchar_unlocked(); for (; c < 48 or c > 57; c = getchar_unlocked()) ; for (; c > 47 && c < 58; c = getchar_unlocked()) x = (x << 3) + (x << 1) + (c & 15); if (neg) x *= -1; } template <typename T> void outp(T n) { bool neg = 0; if (n < 0) n *= -1, neg = 1; char snum[109]; int i = 0; do { snum[i++] = n % 10 + '0'; n /= 10; } while (n); --i; if (neg) putchar_unlocked('-'); while (i >= 0) putchar_unlocked(snum[i--]); putchar_unlocked(' '); } template <typename T, typename... Args> void in(T &num, Args &... args) { inp(num); in(args...); } template <typename T, typename... Args> void out(T first, Args... args) { outp(first); out(args...); } #define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__) const int maxn = 1e7 + 9, mod = 1e9 + 7, nn = 4e3 + 9, oo = 1e9 + 1e8, inf = ~(1 << 31), nmax = 1009, mm = 2e8, filerun = 0; const int maxN = 1e6 + 1; int s[maxN]; int n, m; inline int ReadInt() { char c; for (c = getchar_unlocked(); c < '0' || c > '9'; c = getchar_unlocked()) ; int res = c - '0'; for (c = getchar_unlocked(); c >= '0' && c <= '9'; c = getchar_unlocked()) res = res * 10 + c - '0'; return res; } inline void WriteInt(int x) { if (x > 9) WriteInt(x / 10); putchar_unlocked(x % 10 + '0'); } inline bool Odd(int x) { return x & 1; } struct TSegmentTree { typedef int TTreeArr[maxN << 2]; TTreeArr L, H, sumV, minV; int leaf[maxN]; void Build(int x, int low, int high) { L[x] = low; H[x] = high; if (low == high) { leaf[low] = x; sumV[x] = minV[x] = s[low]; } else { int middle = (low + high) >> 1; Build(x << 1, low, middle); Build((x << 1) + 1, middle + 1, high); sumV[x] = sumV[x << 1] + sumV[(x << 1) + 1]; minV[x] = min(minV[x << 1], sumV[x << 1] + minV[(x << 1) + 1]); } } inline void Increase(int i, int Delta) { int x = leaf[i]; sumV[x] += Delta; minV[x] += Delta; for (x >>= 1; x > 0; x >>= 1) { sumV[x] += Delta; minV[x] = min(minV[x << 1], sumV[x << 1] + minV[(x << 1) + 1]); } } inline int GetLastMin(int x) { while (L[x] < H[x]) x = sumV[x << 1] + minV[(x << 1) + 1] == minV[x] ? (x << 1) + 1 : x << 1; return L[x]; } int FindMatch(int i) { --i; int t = 0; int y = -1, z = -1, ty; for (int x = leaf[i]; x > 0; x >>= 1) if (!Odd(x)) { if (minV[x + 1] + t < 0) { y = x + 1; ty = t; break; } else if (minV[x + 1] + t == 0) z = x + 1; t += sumV[x + 1]; } if (y != -1) { while (L[y] < H[y]) if (minV[y << 1] + ty < 0) y <<= 1; else { if (minV[y << 1] + ty == 0) z = y << 1; ty += sumV[y << 1]; y = (y << 1) + 1; } } return z == -1 ? i : GetLastMin(z); } } tree; inline void PerformFlip(int i) { s[i] = -s[i]; tree.Increase(i, s[i] == 1 ? 2 : -2); } inline int PerformQuery(int i) { return tree.FindMatch(i) - i + 1; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); n = 0; s[0] = 0; char c; for (c = getchar_unlocked(); c == '(' || c == ')'; c = getchar_unlocked()) s[++n] = c == '(' ? 1 : -1; tree.Build(1, 0, n); m = ReadInt(); for (; m > 0; --m) { char c; for (c = getchar_unlocked(); c != 'C' && c != 'Q'; c = getchar_unlocked()) ; if (c == 'C') PerformFlip(ReadInt()); else { WriteInt(PerformQuery(ReadInt())); putchar_unlocked('\n'); } } }