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

Пам'ятаєте першу задачу? Ця задача дуже схожа.

Дано шахівниця розміром $n\times m$. Тобто з $n$ рядками та $m$ стовпчиками.

У цій шахівниці є фігура — тура. Вона знаходиться у нижньому лівому куті, яка має координати $(1,1)$. Протилежний кут має координати $(n,m)$. Також дано $k$ інших фігур. $i$-та фігура має координати $(x_i,y_j)$, де $1\le x_i\le n$, $1\le y_i\le m$.

Порахуйте кількість клітин, на які може переміститися тура не більше, ніж за два ходи. Зверніть увагу, що позицію, на які зараз тура, рахувати непотрібно. Тура не може бити інші фігури, а також не може перескакувати через них. Інші фігури не рухаються.

Giriş verilənləri

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

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

Çıxış verilənləri

Виведіть одне ціле число.

Nümunələr

Qeyd

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

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

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

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

Qiymətləndirmə

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

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