#include #ifdef LOCAL #include #else #define debug(...) void(0) #endif struct Mo { Mo(int n) : n(n) {} void add(int l, int r) { assert(l <= r); left.emplace_back(l); right.emplace_back(r); } template void run(const AL& add_left, const AR& add_right, const DL& del_left, const DR del_right, const REM& rem) { int q = left.size(), width = n / std::min(std::max(sqrt(q * 2 / 3), 1), n); std::vector order(q); std::iota(order.begin(), order.end(), 0); std::sort(order.begin(), order.end(), [&](int a, int b) { int ablock = left[a] / width, bblock = left[b] / width; if (ablock != bblock) return ablock < bblock; return (ablock & 1) ? (right[a] > right[b]) : (right[a] < right[b]); }); int l = 0, r = 0; for (auto idx : order) { while (l > left[idx]) add_left(--l); while (r < right[idx]) add_right(r++); while (l < left[idx]) del_left(l++); while (r > right[idx]) del_right(--r); rem(idx); } } template void run(const A& add, const D& del, const REM& rem) { run(add, add, del, del, rem); } private: int n; std::vector left, right; }; using namespace std; typedef long long ll; #define all(x) begin(x), end(x) constexpr int INF = (1 << 30) - 1; constexpr long long IINF = (1LL << 60) - 1; constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; template istream& operator>>(istream& is, vector& v) { for (auto& x : v) is >> x; return is; } template ostream& operator<<(ostream& os, const vector& v) { auto sep = ""; for (const auto& x : v) os << exchange(sep, " ") << x; return os; } template bool chmin(T& x, U&& y) { return y < x and (x = forward(y), true); } template bool chmax(T& x, U&& y) { return x < y and (x = forward(y), true); } template void mkuni(vector& v) { sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v)); } template int lwb(const vector& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, Q; cin >> N >> M >> Q; vector P(N), S(N); for (int i = 0; i < N; i++) { string tmp; cin >> P[i] >> tmp; P[i]--; S[i] = (tmp == "AC"); } Mo mo(N); for (int i = 0; i < Q; i++) { int L, R; cin >> L >> R; mo.add(--L, R); } vector cnt(M, 0), nxt(N, 0); for (int i = N - 1; i >= 0; i--) { if (S[i] == 0) cnt[P[i]]++; else { nxt[i] = cnt[P[i]]; cnt[P[i]] = 0; } } vector> ans(Q); int AC = 0, penalty = 0; vector ac(M, 0), wa(M, 0); auto add_left = [&](int idx) { int p = P[idx]; if (S[idx] == 0) { if (ac[p]) penalty++; wa[p]++; } else { if (ac[p] == 0) AC++; else penalty -= nxt[idx]; ac[p]++; } }; auto add_right = [&](int idx) { int p = P[idx]; if (S[idx] == 0) { wa[p]++; } else { if (ac[p] == 0) { AC++; penalty += wa[p]; } ac[p]++; } }; auto del_left = [&](int idx) { int p = P[idx]; if (S[idx] == 0) { if (ac[p]) penalty--; wa[p]--; } else { ac[p]--; if (ac[p] == 0) AC--; else penalty += nxt[idx]; } }; auto del_right = [&](int idx) { int p = P[idx]; if (S[idx] == 0) { wa[p]--; } else { ac[p]--; if (ac[p] == 0) { AC--; penalty -= wa[p]; } } }; auto rem = [&](int idx) { ans[idx] = {AC, penalty}; }; mo.run(add_left, add_right, del_left, del_right, rem); for (auto [x, y] : ans) cout << x << ' ' << y << '\n'; return 0; }