Задача #bav0004

Задача продублирована в pdf во вложении

Однажды, после неудачно написанного контеста на Codeforces, Михаил окончательно разочаровался в своей карьере программиста и решил устроиться на работу дворником. Однако, даже на такую должность его ждало собеседование.

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

n

строк и

m

столбцов. Строки пронумерованы сверху вниз числами от

1

до

n

, а столбцы — слева направо числами от

1

до

m

. На пересечении

i

-й строки и

j

-го столбца находится клетка с координатами

(

i

,

j

)

.

Изначально в каждой клетке двора лежит огромная куча мусора. Михаил в рамках своего собеседования произвел

k

операций, каждая из которых была одного из двух типов:

Убрать весь мусор во всех клетках

(

i

,

j

)

, таких что

i

+

j

=

s

;

Убрать весь мусор во всех клетках

(

i

,

j

)

, таких что

i

−

j

=

d

.

Ваша задача — определить количество клеток, в которых Михаил убрал весь мусор.

Формат входных данных

Первая строка содержит два целых числа

n

и

m

(

1

≤

n

,

m

≤

10

9

) — размеры двора.

Вторая строка содержит одно целое число

k

(

0

≤

k

≤

300

000

) — количество операций, совершенных Михаилом.

Каждая из следующих

k

строк содержит описание очередной операции, совершенной Михаилом в следующем формате:

+ s (

2

≤

s

≤

n

+

m

) — данная операция означает, что Михаил убрал весь мусор во всех клетках

(

i

,

j

)

, таких что

i

+

j

=

s

;

- d (

1

−

m

≤

d

≤

n

−

1

) — данная операция означает, что Михаил убрал весь мусор во всех клетках

(

i

,

j

)

, таких что

i

−

j

=

d

.

Формат выходных данных

Выведите одно целое число — количество клеток, в которых Михаил убрал весь мусор.