#line 1 "c.cpp" #include #include #define rep(i,n) for (int i = 0; i < int(n); ++i) #define repp(i,m,n) for (int i = m; i < int(n); ++i) #define reb(i,n) for (int i = int(n)-1; i >= 0; --i) #define all(v) v.begin(),v.end() using namespace std; using namespace atcoder; using ll = long long; using ull = unsigned long long; using ld = long double; using P = pair; using PL = pair; using pdd = pair; using pil = pair; using pli = pair; templateistream &operator>>(istream &is,vector &v){for(auto &e:v)is>>e;return is;} templatebool range(T a,T b,T x){return (a<=x&&xbool rrange(T a,T b,T c,T d,T x,T y){return (range(a,c,x)&&range(b,d,y));} template T rev(const T& str_or_vec){T res = str_or_vec; reverse(res.begin(),res.end()); return res; } templatebool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;} templatebool chmax(T &a,const T &b){if(avoid uniq(vector &v){sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());} templatevoid print(pair a); templatevoid print(vector v); templatevoid print(vector> v); void print(){ putchar(' '); } void print(bool a){ printf("%d", a); } void print(int a){ printf("%d", a); } void print(long a){ printf("%ld", a); } void print(long long a){ printf("%lld", a); } void print(char a){ printf("%c", a); } void print(char a[]){ printf("%s", a); } void print(const char a[]){ printf("%s", a); } void print(long double a){ printf("%.15Lf", a); } void print(const string& a){ for(auto&& i : a) print(i); } void print(unsigned int a){ printf("%u", a); } void print(unsigned long long a) { printf("%llu", a); } template void print(const T& a){ cout << a; } int out(){ putchar('\n'); return 0; } template int out(const T& t){ print(t); putchar('\n'); return 0; } template int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; } templatevoid print(pair a){print(a.first);print(),print(a.second);} templatevoid print(vector v){for(auto ite=v.begin();ite!=v.end();){print(*ite);if(++ite!=v.end())print();}} templatevoid print(vector> v){for(auto ite=v.begin();ite!=v.end();){print(*ite);if(++ite!=v.end())out();}} void yes(){out("Yes");} void no (){out("No");} void yn (bool t){if(t)yes();else no();} void fast_io(){cin.tie(0); ios::sync_with_stdio(0); cout< dx = {0,1,0,-1,1,1,-1,-1}; const vector dy = {1,0,-1,0,1,-1,-1,1}; const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string alp = "abcdefghijklmnopqrstuvwxyz"; const string NUM = "0123456789"; } // namespace noya2 using namespace noya2; using mint = modint998244353; //using mint = modint1000000007; //using mint = modint; void out(mint a){out(a.val());} void out(vector a){vector b(a.size()); rep(i,a.size()) b[i] = a[i].val(); out(b);} void out(vector> a){for (auto v : a) out(v);} #line 2 "Mo.hpp" /* usage : https://nyaannyaan.github.io/library/modulo/multipoint-binomial-sum.hpp */ #line 12 "Mo.hpp" namespace noya2{ struct Mo { int width; std::vector left, right, order; Mo(int N, int Q): order(Q) { width = std::max(1, 1.0 * N / std::max(1.0, std::sqrt(Q * 2.0 / 3.0))); std::iota(begin(order), end(order), 0); } void insert(int l, int r) { /* [l, r) */ left.emplace_back(l); right.emplace_back(r); } template void run(const AL& add_left, const AR& add_right, const DL& delete_left, const DR& delete_right, const REM& rem) { assert(left.size() == order.size()); sort(begin(order), end(order), [&](int a, int b) { int ablock = left[a] / width, bblock = left[b] / width; if (ablock != bblock) return ablock < bblock; if (ablock & 1) return right[a] < right[b]; return right[a] > right[b]; }); int nl = 0, nr = 0; for (auto idx : order) { while (nl > left[idx]) add_left(--nl); while (nr < right[idx]) add_right(nr++); while (nl < left[idx]) delete_left(nl++); while (nr > right[idx]) delete_right(--nr); rem(idx); } } }; } #line 77 "c.cpp" int op(int a, int b){ return max(a,b); } int e(){ return 0; } bool f(int x){ return x == 0; } void solve(){ int n, m, q; cin >> n >> m >> q; segtree seg(n); vector> a(m), b(m); vector c(n), d(n); rep(i,n){ int p; cin >> p; p--; string s; cin >> s; c[i] = p; d[i] = a[p].size(); a[p].emplace_back(i); b[p].emplace_back(s == "AC" ? 1 : 0); } int id = 0; vector pres(m,0); rep(i,m){ int siz = a[i].size(); rep(j,siz){ seg.set(id++,b[i][j]); } if (i != m-1) pres[i+1] = pres[i] + siz; } int ac = 0, wa = 0; vector ls(m,0), rs(m,0); auto eval = [&](int i){ int l = pres[i] + ls[i]; int r = pres[i] + rs[i]; if (seg.prod(l,r) == 0) return P(0,0); return P(1,seg.max_right(l)-l); }; auto add = [&](int i){ auto [xac, xwa] = eval(i); ac += xac, wa += xwa; }; auto del = [&](int i){ auto [xac, xwa] = eval(i); ac -= xac, wa -= xwa; }; auto adl = [&](int idx){ int i = c[idx]; del(i); ls[i]--; add(i); }; auto adr = [&](int idx){ int i = c[idx]; del(i); rs[i]++; add(i); }; auto dll = [&](int idx){ int i = c[idx]; del(i); ls[i]++; add(i); }; auto dlr = [&](int idx){ int i = c[idx]; del(i); rs[i]--; add(i); }; vector acs(q), was(q); auto memo = [&](int i){ acs[i] = ac, was[i] = wa; }; Mo mo(n,q); rep(i,q){ int l, r; cin >> l >> r; l--; mo.insert(l,r); } mo.run(adl,adr,dll,dlr,memo); rep(i,q){ out(acs[i],was[i]); } } int main(){ fast_io(); int t = 1; //cin >> t; while(t--) solve(); }