Bubbles

Interview

Time limit1sMemory limit256 MB

Summary

Each person sits in one of P personal bubbles and one of W work bubbles, every personal bubble meets every work bubble in exactly one person; given infected bubbles, count infected people.

Level: Medium5 of 10
Topics: Union-find, Graph, Math, Implementation
Solved: No attempts yet

Problem

Bubbles are a popular method of controlling the spread of disease. Each person chooses a bubble of other people to associate with and avoids contact with others. An infection in one bubble should not spread to people in other bubbles.

The concept fails, however, when a person belongs to multiple bubbles. For example, a person might have a personal bubble of family and friends and a work bubble of colleagues. In this problem, we make the following simplifying assumptions:

Each personal bubble contains the same number of people, P.
Each work bubble contains the same number of people, W.
Each person is in exactly one personal bubble and one work bubble.
Each pair of a personal bubble and a work bubble has exactly one person in common.

Given a list of the bubbles that have been infected, determine how many people have been infected.

Input

First line: three integers P, W, N, the number of people in each personal and work bubble and the number of infected bubbles. These numbers satisfy the constraints 1 ≤ P, W ≤ 200, 000 and 0 ≤ N ≤ min(P + W, 10 000). Next N lines: the letter P or W, a space, and an integer B, indicating that personal or work bubble number B is infected. When the letter is P, B satisfies the constraint 0 ≤ B < W. When the letter is W, B satisfies the constraint 0 ≤ B < P. Each infected bubble is listed only once.

Output

A single integer I, the total number of people infected.

Examples1

Example 1
Input
```
2 3 2
W 1
P 1
```
Expected output
```
4
```