Вы участвуете в испытаниях нового оружия. Для испытаний создан полигон, представляющий собой прямоугольное поле размера n × m, разделенное на единичные квадраты 1 × 1. На полигоне расположено k объектов, каждый из которых является прямоугольником со сторонами, параллельными сторонам полигона, занимающим полностью несколько единичных квадратов. Объекты не пересекаются и не касаются друг друга.
Принцип действия оружия сверхсекретен. Вам известно лишь то, что с помощью него можно нанести удар по любой прямоугольной области ненулевой площади со сторонами, параллельными сторонам полигона. Область должна накрывать полностью некоторые из единичных квадратов, на которые разбит полигон, и никак не затрагивать остальные квадраты. Разумеется, область не должна выходить за границы полигона. При этом вам поставлена задача: поразить не менее одного и не более трех прямоугольных объектов. Каждый объект должен лежать либо целиком внутри области (тогда он считается пораженным), либо целиком вне области.
Посчитайте количество способов нанести удар.
Выходные данные
Выведите единственное число — количество способов нанести удар.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 3
*.*
...
*..
|
21
|
|
2
|
4 5 4
.*.**
...**
**...
...**
|
38
|
|
3
|
2 2 1
.*
..
|
4
|