Пам'ятаєте першу задачу? Ця задача дуже схожа.
Дано шахівниця розміром $$$n \times m$$$. Тобто з $$$n$$$ рядками та $$$m$$$ стовпчиками.
У цій шахівниці є фігура — тура. Вона знаходиться у нижньому лівому куті, яка має координати $$$(1, 1)$$$. Протилежний кут має координати $$$(n, m)$$$. Також дано $$$k$$$ інших фігур. $$$i$$$-та фігура має координати $$$(x_i, y_j)$$$, де $$$1 \leq x_i \leq n$$$, $$$1 \leq y_i \leq m$$$.
Порахуйте кількість клітин, на які може переміститися тура не більше, ніж за два ходи. Зверніть увагу, що позицію, на які зараз тура, рахувати непотрібно. Тура не може бити інші фігури, а також не може перескакувати через них. Інші фігури не рухаються.
Перший рядок містить три цілі числа $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 2 \cdot 10^5$$$).
Кожен з наступних $$$k$$$ рядків містить два цілі числа $$$x_i$$$ та $$$y_i$$$ ($$$1 \leq x_i \leq n$$$, $$$1 \leq y_i \leq m$$$). Гарантується, що всі фігури, включно з турою, знаходяться на різних позиціях.
Виведіть одне ціле число.
У $$$60\%$$$ тестів виконуються обмеження $$$n, m \leq 1\,000$$$.
У $$$80\%$$$ тестів виконуються обмеження $$$n, m \leq 10\,000$$$.
3 3 2 2 3 3 2
5
3 3 0
8
4 4 2 1 2 2 1
0
4 5 2 3 1 2 4
14
У першому прикладі можна потрапити у клітини $$$[(1, 2), (1, 3), (2, 1), (2, 2), (3, 1)]$$$.
У другому прикладі можна потрапити в усі клітини.
У третьому прикладі не можна потрапити у жодну клітину.
Четвертий приклад пояснений нижче. Тут $$$T$$$ — тура. $$$X$$$ — фігура. $$$1$$$ — позиція, яку можна досягти. $$$0$$$ — позиція, яку неможливо досягти.
$$$$$$ \begin{matrix} 0 & 1 & 1 & 0 & 1 \\ X & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & X & 1 \\ T & 1 & 1 & 1 & 1 \\ \end{matrix} $$$$$$