#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; }; template struct BinaryIndexedTree { BinaryIndexedTree() : n(0) {} BinaryIndexedTree(int n) : n(n), data(n) {} void add(int k, T x) { assert(0 <= k && k < n); for (k++; k <= n; k += k & -k) data[k - 1] += x; } T query(int l, int r) const { assert(0 <= l && l <= r && r <= n); return sum(r) - sum(l); } T operator[](int i) const { return query(i, i + 1); } int lower_bound(T x) const { if (x <= 0) return 0; int cur = 0, k = 1; while (k < n) k <<= 1; for (; k > 0; k >>= 1) { if (cur + k <= n && data[cur + k - 1] < x) { x -= data[cur + k - 1]; cur += k; } } return cur; } int upper_bound(T x) const { return lower_bound(x + 1); } private: int n; std::vector data; T sum(int r) const { T res = 0; for (; r > 0; r -= r & -r) res += data[r - 1]; return res; } }; using namespace std; #include using namespace std; using namespace std; namespace internal { template using is_broadly_integral = typename conditional_t || is_same_v || is_same_v, true_type, false_type>::type; template using is_broadly_signed = typename conditional_t || is_same_v, true_type, false_type>::type; template using is_broadly_unsigned = typename conditional_t || is_same_v, true_type, false_type>::type; #define ENABLE_VALUE(x) template constexpr bool x##_v = x::value; ENABLE_VALUE(is_broadly_integral); ENABLE_VALUE(is_broadly_signed); ENABLE_VALUE(is_broadly_unsigned); #undef ENABLE_VALUE #define ENABLE_HAS_TYPE(var) \ template struct has_##var : std::false_type {}; \ template struct has_##var> : std::true_type {}; \ template constexpr auto has_##var##_v = has_##var::value; } // namespace internal namespace fastio { static constexpr int SZ = 1 << 17; static constexpr int offset = 64; char inbuf[SZ], outbuf[SZ]; int in_left = 0, in_right = 0, out_right = 0; struct Pre { char num[40000]; constexpr Pre() : num() { for (int i = 0; i < 10000; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i * 4 + j] = n % 10 + '0'; n /= 10; } } } } constexpr pre; void load() { int len = in_right - in_left; memmove(inbuf, inbuf + in_left, len); in_right = len + fread(inbuf + len, 1, SZ - len, stdin); in_left = 0; } void flush() { fwrite(outbuf, 1, out_right, stdout); out_right = 0; } void skip_space() { if (in_left + offset > in_right) load(); while (inbuf[in_left] <= ' ') in_left++; } void single_read(char& c) { if (in_left + offset > in_right) load(); skip_space(); c = inbuf[in_left++]; } void single_read(string& S) { skip_space(); while (true) { if (in_left == in_right) load(); int i = in_left; for (; i != in_right; i++) { if (inbuf[i] <= ' ') break; } copy(inbuf + in_left, inbuf + i, back_inserter(S)); in_left = i; if (i != in_right) break; } } template >* = nullptr> void single_read(T& x) { if (in_left + offset > in_right) load(); skip_space(); char c = inbuf[in_left++]; [[maybe_unused]] bool minus = false; if constexpr (internal::is_broadly_signed_v) { if (c == '-') minus = true, c = inbuf[in_left++]; } x = 0; while (c >= '0') { x = x * 10 + (c & 15); c = inbuf[in_left++]; } if constexpr (internal::is_broadly_signed_v) { if (minus) x = -x; } } void rd() {} template void rd(Head& head, Tail&... tail) { single_read(head); rd(tail...); } void single_write(const char& c) { if (out_right > SZ - offset) flush(); outbuf[out_right++] = c; } void single_write(const bool& b) { if (out_right > SZ - offset) flush(); outbuf[out_right++] = b ? '1' : '0'; } void single_write(const string& S) { int i = 0; while (i != (int)S.size()) { if (out_right == SZ) flush(); int len = min((int)S.size() - i, SZ - out_right); memcpy(outbuf + out_right, S.data() + i, sizeof(char) * len); i += len, out_right += len; } } void single_write(const char* p) { int i = 0, N = strlen(p); while (i != N) { if (out_right == SZ) flush(); int len = min(N - i, SZ - out_right); memcpy(outbuf + out_right, p + i, sizeof(char) * len); i += len, out_right += len; } } template >* = nullptr> void single_write(const T& _x) { if (out_right > SZ - offset) flush(); if (_x == 0) { outbuf[out_right++] = '0'; return; } T x = _x; if constexpr (internal::is_broadly_signed_v) { if (x < 0) outbuf[out_right++] = '-', x = -x; } constexpr int buffer_size = sizeof(T) * 10 / 4; char buf[buffer_size]; int i = buffer_size; while (x >= 10000) { i -= 4; memcpy(buf + i, pre.num + (x % 10000) * 4, 4); x /= 10000; } if (x < 100) { if (x < 10) { outbuf[out_right] = '0' + x; ++out_right; } else { uint32_t q = (uint32_t(x) * 205) >> 11; uint32_t r = uint32_t(x) - q * 10; outbuf[out_right] = '0' + q; outbuf[out_right + 1] = '0' + r; out_right += 2; } } else { if (x < 1000) { memcpy(outbuf + out_right, pre.num + (x << 2) + 1, 3); out_right += 3; } else { memcpy(outbuf + out_right, pre.num + (x << 2), 4); out_right += 4; } } memcpy(outbuf + out_right, buf + i, buffer_size - i); out_right += buffer_size - i; } void wt() {} template void wt(const Head& head, const Tail&... tail) { single_write(head); wt(forward(tail)...); } template void wtn(const Args&... x) { wt(forward(x)...); wt('\n'); } struct Dummy { Dummy() { atexit(flush); } } dummy; } // namespace fastio using fastio::rd; using fastio::skip_space; using fastio::wt; using fastio::wtn; 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; rd(N); rd(M); rd(Q); vector P(N), S(N); for (int i = 0; i < N; i++) { string tmp; rd(P[i]); rd(tmp); P[i]--; S[i] = (tmp == "AC"); } Mo mo(N); for (int i = 0; i < Q; i++) { int L, R; rd(L); rd(R); mo.add(--L, R); } vector> cand(M); for (int i = 0; i < N; i++) cand[P[i]].emplace_back(i); vector> ac(M), wa(M); vector ord(N), sum(M, 0); for (int i = 0; i < N; i++) ord[i] = lwb(cand[P[i]], i); for (int i = 0; i < M; i++) { ac[i] = BinaryIndexedTree(cand[i].size()); wa[i] = BinaryIndexedTree(cand[i].size()); } int correct = 0, penalty = 0; auto calc = [&](int idx) { if (sum[idx] == 0) return 0; int x = ac[idx].lower_bound(1); return wa[idx].query(0, x); }; auto add = [&](int idx) { int x = P[idx]; { correct -= (sum[x] > 0); penalty -= calc(x); } if (S[idx] == 0) wa[x].add(ord[idx], 1); else { ac[x].add(ord[idx], 1); sum[x]++; } { correct += (sum[x] > 0); penalty += calc(x); } }; auto del = [&](int idx) { int x = P[idx]; { correct -= (sum[x] > 0); penalty -= calc(x); } if (S[idx] == 0) wa[x].add(ord[idx], -1); else { ac[x].add(ord[idx], -1); sum[x]--; } { correct += (sum[x] > 0); penalty += calc(x); } }; vector ans1(Q), ans2(Q); auto rem = [&](int idx) { ans1[idx] = correct; ans2[idx] = penalty; }; mo.run(add, del, rem); for (int i = 0; i < Q; i++) { wt(ans1[i]); wt(' '); wt(ans2[i]); wt('\n'); } return 0; }