Ви знаєте різницю між готелем та мотелем? Ви маєте рацію, різниця в кількості мух, що живуть там. Петя власник одного з найпопулярніших мотелів у Берляндії, але його мама наполягає на тому, щоб він перетворив свій мотель на готель. Саме тому вона подарувала Петі мухобойку у вигляді багатокутника з \(k\) вершин.

Підійшовши до вікна Петя побачив \(n\) мух. Так як Петя і мухи не скривдить, він хоче дізнатися кількість способів вдарити мухобойкою, не покалічивши жодної мухи.

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

Оцінювання

(реалізовано наближено)

• Підзавдання 1 (30 балів)}: \(x_p \cdot y_p \cdot n \cdot k \le 3 \cdot 10^7\) і \(x_p, y_p \le 100\)

• {Підзавдання 2 (20 балів)}: \(x_p, y_p \le 100\)

• {Підзавдання 3 (20 балів)}: мухобійка є прямокутником зі сторонами паралельними осям координат

• {Підзавдання 4 (30 балів)}: немає додаткових обмежень

Примітка

Пояснення до третього прикладу:

Формат вхідних даних

Перший рядок вхідних даних містить числа \(x_p\), \(y_p\) і \(n\) (\(1 \le x_p, y_p \le 500\), \(0 \le n \le x_p \cdot y_p\)) - координати правого верхнього кута вікна та кількість мух на ній, відповідно.

Наступні \(n\) рядків містять два числа \(x\) і \(y\) (\(0 < x < x_p\), \(0 < y < y_p\)) - координати мух на вікні.

Наступний рядок містить число \(k\) (\(3 \le k \le 10\,000\)) - кількість вершин у мухобойки. У наступних \(k\) рядках даються \(x_i\) і \(y_i\) (\(-10^9 \le x_i, y_i \le 10^9\)) - координати \(i\)-й вершини мухобойки. Вершини задані як обхід, отже сусідні вершини і перша і остання вершини з'єднані прямою лінією.

Формат вихідних даних

Виведіть кількість способів ударити мухобойкою так, щоб жодна муха не постраждала.

Приклад вхідних даних

4 5 2
1 3
3 4
4
0 0
2 0
2 2
0 2

Приклад вихідних даних

4

Приклад вхідних даних

5 5 3
1 4
1 3
2 2
3
4 7
6 3
7 6

Приклад вихідних даних

3

Приклад вхідних даних

6 7 2
2 5
4 5
8
1 4
3 3
4 1
5 3
7 4
5 5
4 7
3 5

Приклад вихідних даних

1