Тура, але уже складніша
Пам'ятаєте першу задачу? Ця задача дуже схожа.
Дано шахівниця розміром . Тобто з рядками та стовпчиками.
У цій шахівниці є фігура — тура. Вона знаходиться у нижньому лівому куті, яка має координати . Протилежний кут має координати . Також дано інших фігур. -та фігура має координати , де , .
Порахуйте кількість клітин, на які може переміститися тура не більше, ніж за два ходи. Зверніть увагу, що позицію, на які зараз тура, рахувати непотрібно. Тура не може бити інші фігури, а також не може перескакувати через них. Інші фігури не рухаються.
Вхідні дані
Перший рядок містить три цілі числа , , (, ).
Кожен з наступних рядків містить два цілі числа та (, ). Гарантується, що всі фігури, включно з турою, знаходяться на різних позиціях.
Вихідні дані
Виведіть одне ціле число.
Приклади
Примітка
У першому прикладі можна потрапити у клітини .
У другому прикладі можна потрапити в усі клітини.
У третьому прикладі не можна потрапити у жодну клітину.
Четвертий приклад пояснений нижче. Тут — тура. — фігура. — позиція, яку можна досягти. — позиція, яку неможливо досягти.
Оцінювання
У тестів виконуються обмеження .
У тестів виконуються обмеження .