## https://yukicoder.me/problems/no/2338 import math from collections import deque def main(): N, M, Q = map(int, input().split()) ps = [] for _ in range(N): p, s = input().split() ps.append((int(p) - 1, s)) lr = [] for _ in range(Q): l, r = map(int, input().split()) lr.append((l - 1, r - 1)) # Mo's Algorithm sqrt_n = int(math.sqrt(N)) lr2 = [] for i in range(Q): l, r = lr[i] l0 = l // sqrt_n lr2.append((l0, i, l, r)) lr2.sort(key=lambda x: x[0] * (2 * N) - r) deques = [deque([0]) for _ in range(M)] wa_count = 0 ac_count = 0 for i in range(N): p, s = ps[i] if s == "WA": deques[p][-1] += 1 else: deques[p].append(0) for i in range(M): if len(deques[i]) >= 2: ac_count += 1 wa_count += deques[i][0] class Interval: def __init__(self, ac_count , wa_count, deques, ps): self.ac_count = ac_count self.wa_count = wa_count self.deques = deques self.ps = ps def delete_from_left(self, index): p, s = self.ps[index] deq = self.deques[p] if s == "WA": deq[0] -= 1 if len(deq) > 1: self.wa_count -= 1 else: deq.popleft() self.ac_count -= 1 if len(deq) > 1: self.ac_count += 1 self.wa_count += deq[0] def add_from_left(self, index): p, s = self.ps[index] deq = self.deques[p] if s == "WA": deq[0] += 1 if len(deq) > 1: self.wa_count += 1 else: if len(deq) > 1: w = deq[0] self.wa_count -= w self.ac_count -= 1 deq.appendleft(0) self.ac_count += 1 def delete_from_right(self, index): p, s = self.ps[index] deq = self.deques[p] if s == "WA": deq[-1] -= 1 else: deq.pop() if len(deq) == 1: self.wa_count -= deq[0] self.ac_count -= 1 def add_from_right(self, index): p, s = self.ps[index] deq = self.deques[p] if s == "WA": deq[-1] += 1 else: if len(deq) == 1: self.wa_count += deq[0] self.ac_count += 1 deq.append(0) interval = Interval(ac_count, wa_count, deques, ps) answers = [[0, 0] for _ in range(Q)] left = 0 right = N - 1 for _, q_index, l0, r0 in lr2: while left < l0: interval.delete_from_left(left) left += 1 while l0 < left: left -= 1 interval.add_from_left(left) while right < r0: right += 1 interval.add_from_right(right) while r0 < right: interval.delete_from_right(right) right -= 1 answers[q_index][0] = interval.ac_count answers[q_index][1] = interval.wa_count for i in range(Q): a, w = answers[i] print(a, w) if __name__ == "__main__": main()