Тура, але уже складніша

Input

Перший рядок містить три цілі числа $n$ , $m$ , $k$ ( $1 \leq n, m \leq 2 \cdot 1 0^{5}$ 1 \le n, m \le 2 \cdot 10^5, $0 \leq k \leq 2 \cdot 1 0^{5}$ 0 \le k \le 2 \cdot 10^5).

Кожен з наступних $k$ рядків містить по два цілі числа $x_{i}$ x_i та $y_{i}$ y_i ( $1 \leq x_{i} \leq n$ 1 \le x_i \le n, $1 \leq y_{i} \leq m$ 1 \le y_i \le m). Гарантується, що всі фігури, включаючи туру, перебувають у різних клітинках.

Output

Виведіть одне ціле число — кількість клітин, до яких може потрапити тура не більше ніж за два ходи.

Examples

Example 1

Loading

Example 2

Loading

Example 3

Loading

Example 4

Loading

Note

У першому прикладі можна потрапити у клітини $[(1, 2), (1, 3), (2, 1), (2, 2), (3, 1)]$ [(1, 2), (1, 3), (2, 1), (2, 2), (3, 1)].

У другому прикладі тура може потрапити до всіх клітин.

У третьому прикладі тура не може потрапити до жодної клітини.

Четвертий приклад подано нижче. Тут $T$ — тура, $X$ — інша фігура, $1$ — досяжна клітина, $0$ — недосяжна клітина:

0 X 1 T 11111111 00 X 1 1111

\begin{matrix} 0 & 1 & 1 & 0 & 1 \\ X & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & X & 1 \\ T & 1 & 1 & 1 & 1 \\ \end{matrix}

Scoring

У $60%$ тестів виконується обмеження $n, m \leq 1000$ n, m \le 1\,000.

У $80%$ тестів виконується обмеження $n, m \leq 10000$ n, m \le 10\,000.