Шахове поле

Панночка Анночка нещодавно потрапила на співбесіду в ІТ-компанію. На цій співбесіді їй дали дуже цікаву задачу:

Дівчині дана площина, поділена на одиничні квадрати. Тобто такі, що кожна їхня сторона дорівнює $1$. При чому кожний квадрат пофарбований або у білий, або у чорний колір.

Назвемо площину шаховою з параметрами $n$ і $m$, якщо вона складається з прямокутників, що мають $n$ одиниць у висоту та $m$ одиниць у ширину. Також всі ці прямокутники мають бути пофарбовані або у білий колір, або у чорний. При чому кожен білий прямокутник межує лише з чорними та навпаки "— кожен чорний межує тільки з білими.

Наприклад, наступні площини є шаховими з параметрами $2$ і $3$ (синім зображено вісі координат):

А оці не є:

Як ви вже могли помітити, дуже часто шахових площин з параметрами $n$ і $m$ буває чимало. Задача полягає в тому, щоб сказати, скільки таких є. Ні-і-і-і, це надто легко.

Анночці також дали $k$ квадратів на цій площині та їхні кольори. Паночка має знайти кількість шахових площин з параметрами $n$ і $m$ таких, що квадрати з відповідними координатами мають задані кольори. Допоможіть їй зробити це!

Більш формально, вам дано $k$ трійок чисел: $x_i,y_i,c_i$, де ($x_i,y_i$) — координати лівого нижнього краю квадрата, а $c_i$ дорівнює $0$, якщо цей квадрат має бути пофарбований у чорний колір, і дорівнює $1$, якщо цей квадрат має бути пофарбований у білий колір. Потрібно вивести кількість різних шахових площин з параметрами $n$ і $m$, які підходять під ці обмеження. Дві шахові площини вважаються різними, якщо існує хоч один квадрат, що пофарбований у різні кольори на цих площинах.

Вхідні дані

Перший рядок містить чотири цілі числа $n$, $m$, $k$, $g$ ($1\le k\le 10^5$, $1\le n,m\le 10^9$, $0\le g\le 4$) — висота кожного прямокутника, ширина кожного прямокутника, кількість відомих точок та номер блоку.

Кожен з наступних $k$ рядків містить по три цілі числа $x_i$, $y_i$, $c_i$ ($1\le x_i,y_i\le 10^9,0\le c_i\le 1$) — координати та колір квадрату. Зауважте, що координати точок можуть повторюватись.

Вихідні дані

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

Приклади

Примітка

Зліва зображення єдиної площини, яка підходить під обмеження прикладу $1$.

Справа "— одна з можливих $8$ площин, які задовольняють умови прикладу $2$.

(Синім позначено осі координат, світло-сірим "— квадратики, які за умовою мають бути білими, темно-сірим "— квадратики, які за умовою мають бути чорними).

Оцінювання

• ($17$ балів): $1\le n,m,x_i,y_i,k\le 100$;

• ($24$ бали): $1\le n,m,k\le 100$;

• ($31$ бал): $1\le n\cdot m\le 10^5,1\le k\le 10^4$;

• ($28$ балів): без додаткових обмежень.