#include #include #include #include #include using namespace std; using i64 = long long; #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++) #define all(x) x.begin(),x.end() #define STRINGIFY(n) #n #define TOSTRING(n) STRINGIFY(n) #define PREFIX "#" TOSTRING(__LINE__) "| " #define debug(x) \ { \ std::cout << PREFIX << #x << " = " << x << std::endl; \ } std::ostream& output_indent(std::ostream& os, int ind) { for(int i = 0; i < ind; i++) os << " "; return os; } template std::ostream& operator<<(std::ostream& os, const std::pair& p); template std::ostream& operator<<(std::ostream& os, const std::vector& v); template std::ostream& operator<<(std::ostream& os, const std::pair& p) { return (os << "(" << p.first << ", " << p.second << ")"); } template std::ostream& operator<<(std::ostream& os, const std::vector& v) { os << "["; for(int i = 0;i < v.size();i++) os << v[i] << ", "; return (os << "]"); } template static inline std::vector ndvec(size_t&& n, T val) { return std::vector(n, std::forward(val)); } template static inline auto ndvec(size_t&& n, Tail&&... tail) { return std::vector(tail)...))>(n, ndvec(std::forward(tail)...)); } #include using i64 = long long; template struct segment_tree { i64 n; std::vector node; segment_tree() {} segment_tree(const std::vector& init) { n = 1; while(n < init.size()) n *= 2; node.resize(2 * n, ide()); for(int i = 0;i < init.size();i++) node[i + n] = init[i]; for(int i = n; i --> 1;) node[i] = ope(node[i * 2], node[i * 2 + 1]); } void update(i64 i, T x) { i += n; node[i] = x; while(i > 1) { i >>= 1; node[i] = ope(node[i * 2], node[i * 2 + 1]); } } T sum(i64 l, i64 r) const { T lx = ide(); T rx = ide(); l += n; r += n; while(l < r) { if(l & 1) { lx = ope(lx, node[l++]); } if(r & 1) { rx = ope(node[--r], rx); } l >>= 1; r >>= 1; } return ope(lx, rx); } const T& at(i64 i) const { return node[i + n]; } template i64 subtree_down_first(i64 i, T lx, F isok) const { while(i < n) { T next = ope(lx, node[i * 2]); if(isok(next)) i = i * 2; else { lx = next; i = i * 2 + 1; } } return i - n + 1; } template i64 find_first(i64 l, F isok) const { if(isok(ide())) { return l; } if(l == 0) { if(isok(node[1])) return subtree_down_first(1, ide(), isok); return -1; } T lx = ide(); i64 r = n << 1; l += n; while(l < r) { if(l & 1) { T next = ope(lx, node[l]); if(isok(next)) return subtree_down_first(l, lx, isok); lx = next; l++; } l >>= 1; r >>= 1; } return -1; } }; int a_i() { return 0; } int a_o(int a, int b) { return a + b; } using Seg = segment_tree; int main() { int N, M, Q; cin >> N >> M >> Q; std::vector P, S; P.resize(N); S.resize(N); for(int i = 0; i < N; i++) { int p; string s; cin >> p >> s; P[i] = p - 1; S[i] = s == "AC" ? 1 : 0; } std::vector>> query(N); for(int i = 0; i < Q; i++) { int a, b; cin >> a >> b; a--; b--; query[a].push_back({ b, i }); } vector before(M, -1); vector>> was(M, vector>(1)); vector> ac(M); vector> acs(N); vector wi(M, 0); for(int i = 0; i < N; i++) { int p = P[i]; if(S[i] == 0) { was[p].back().push_back(i); } else { ac[p].push_back(i); acs[i].push_back(p); was[p].push_back({}); } } Seg seg_a(std::vector(N, 0)); Seg seg_w(std::vector(N, 0)); for(int p = 0; p < M; p++) { was[p].pop_back(); if(wi[p] < was[p].size()) { seg_a.update(ac[p][wi[p]], 1); for(auto i: was[p][wi[p]]) { seg_w.update(i, 1); } } } std::vector> ans(Q); for(int i = 0; i < N; i++) { for(auto [r, q]: query[i]) { ans[q] = { seg_a.sum(i, r + 1), seg_w.sum(i, r + 1) }; } for(auto p: acs[i]) { seg_a.update(ac[p][wi[p]], 0); for(auto i: was[p][wi[p]]) { seg_w.update(i, 0); } wi[p]++; if(wi[p] < was[p].size()) { seg_a.update(ac[p][wi[p]], 1); for(auto i: was[p][wi[p]]) { seg_w.update(i, 1); } } } } for(auto [a, b]: ans) { cout << a << " " << b << endl; } }