#include using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); int n, m, q; cin >> n >> m >> q; vector p(n), s(n); for (int i = 0; i < n; i++) { cin >> p[i]; --p[i]; string x; cin >> x; s[i] = (x == "AC"); } vector> ind(m); vector rev(n); for (int i = 0; i < n; i++) { rev[i] = ind[p[i]].size(); ind[p[i]].push_back(i); } vector> queries(q); int idx = 0; for (auto &[l, r, id] : queries) { cin >> l >> r; --l; id = idx++; } const int SQ = sqrt(n); sort(queries.begin(), queries.end(), [&](auto &a, auto &b) { if (get<0>(a) / SQ != get<0>(b) / SQ) return get<0>(a) < get<0>(b); return get<1>(a) < get<1>(b); }); vector acs(q), penalty(q); vector ptl(m), ptr(m, 0); int tot_ac = 0, tot_penalty = 0; vector> cnt_ac(m), prox_ac(m); vector cur_penalty(m); for (int c = 0; c < m; c++) { auto &ac = cnt_ac[c]; ac = ind[c]; for (auto &i : ac) i = s[i]; ac.push_back(0); for (int i = ac.size() - 2; i >= 0; --i) ac[i] += ac[i + 1]; auto &prox = prox_ac[c]; prox.resize(ind[c].size()); int nxt = -1; for (int i = prox.size() - 1; i >= 0; --i) { int j = ind[c][i]; prox[i] = nxt; if (s[j]) nxt = i; } } auto insert = [&] (int i) { //cout << "insert " << i << endl; int c = p[i]; int& pen = cur_penalty[c]; int id_i = rev[i]; int tem_ac = cnt_ac[c][ptl[c]] - cnt_ac[c][ptr[c]]; tot_penalty -= pen; if (ptr[c] == id_i) { if (!tem_ac && s[i]) { tot_ac++; pen = ptr[c] - ptl[c]; } ptr[c]++; } else { assert(id_i + 1 == ptl[c]); if (!s[i]) { if (tem_ac) pen++; } else { if (!tem_ac) tot_ac++; pen = 0; } ptl[c]--; } tot_penalty += pen; //cout << "? tot_ac = " << tot_ac << " tot_penalty = " << tot_penalty << endl; }; auto erase = [&] (int i) { //cout << "erase " << i << endl; int c = p[i]; int& pen = cur_penalty[c]; int id_i = rev[i]; int tem_ac = cnt_ac[c][ptl[c]] - cnt_ac[c][ptr[c]]; tot_penalty -= pen; if (ptl[c] == id_i) { if (s[i]) { if (tem_ac == 1) pen = 0, --tot_ac; else { int nxt = prox_ac[c][id_i]; assert(~nxt); pen = nxt - id_i - 1; } } else { if (tem_ac) pen--; } ptl[c]++; } else { assert(id_i + 1 == ptr[c]); if (s[i] && tem_ac == 1) pen = 0, --tot_ac; ptr[c]--; } tot_penalty += pen; //cout << "? tot_ac = " << tot_ac << " tot_penalty = " << tot_penalty << endl; }; int l = 0, r = 0; for (auto [lx, rx, id] : queries) { while (lx < l) insert(--l); while (r < rx) insert(r++); while (rx < r) erase(--r); while (l < lx) erase(l++); //cout << "responde " << lx << " " << rx << endl; acs[id] = tot_ac; penalty[id] = tot_penalty; } for (int i = 0; i < q; i++) { cout << acs[i] << " " << penalty[i] << endl; } }