eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Klingon Battle Bagel

Klingon Battle Bagel

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Two opponents play a game on a checkered field of size N×M. The first player places several shapes of "Klingon battle bagel" spaceship in the field. The shape of the ship is a solid 3×3 square having a hole in the center (see Fig.). Ships can touch the edges of the field and each other but cannot intersect.

The second player tries to find all the ships, firing at the cells of the field.

The second player has made K shots at different cells hitting the ships, and F shots at other cells that missed.

Write program to calculate the minimum and the maximum number of ships that can be located in the field.

Входные данные

The number of rows N and the number of columns M (1N, M100000) of the playing field are given in the first line of the input file, separated with a space character.

The second line contains the number of hits H and the number of misses F (0H, F N×M, 0H+FN×M).

Выходные данные

Space-delimited values of the minimum and the maximum number of ships possibly located on the field.

Output "BAZINGA!" (without quotation marks) if no solution exists for the input data.

Пример

Входные данные #1
7 7
1 1
Выходные данные #1
1 4
Источник 2013-2014 ACM Central Region of Russia Quarterfinal, Rybinsk 2013/10/17