ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1923. Про политику

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Мир в опасности. Ещё совсем недавно отношения между двумя сильнейшими империями — Кразилией и Хексикой — были лишь слегка натянутыми, а теперь мир стоит на пороге очередной мировой войны. Кразилия и Хексика — политически продвинутые страны, а потому перед тем, как вступить в военные действия, они аккуратно вербуют себе союзников.
На момент начала вербовки каждая из стран мира принадлежала к одному из 10 союзов. В рамках подготовки к войне каждая из враждующих империй действует следующим образом: сначала она выбирает один из союзов (отличный от того, в который она входит в текущий момент) и вступает в него. После этого все страны данного союза, которые граничат с этой империей, присоединяются к ней. Когда присоединение новых территорий завершено, империя перестаёт предпринимать какие-либо действия и ждёт, пока страна-соперник сделает свой политический ход. Естественно, ни одна из враждующих стран не будет вступать в союз, в который в настоящее время входит вражеская империя. Вступая в новый союз Кразилия и Хексика выходят из союза, в котором состояли до этого. При этом ранее присоединившиеся территории не выходят из состава империи, поэтому с каждым днем противодействие империй все больше угрожает человечеству.
К счастью, в мире есть один Гениальный Политик, который не спешит поддерживать какую-либо империю. Он готов разработать план по спасению мира, но для этого ему нужно знать, какова площадь территорий Кразилии и Хексики на данный момент. У вас есть запись того, в какие союзы и в каком порядке вступали империи в период вербовки. Помогите спасти мир — предоставьте Гениальному Политику нужную информацию.

Исходные данные

Карта мира представляет собой прямоугольник n × m, расчерченный на клетки 1 × 1. В первой строке через пробел даны целые числа n и m — размеры карты мира (2 ≤ n, m ≤ 50). Каждая из следующих n строк содержит m цифр (от 0 до 9). Каждая цифра обозначает номер союза, которому принадлежит территория, соответствующая данной клетке карты. Область соседних клеток, состоящих в одном союзе, образуют страну. Соседними клетками на карте называются клетки, имеющие общую сторону. Если две соседние клетки состоят в одном союзе, то они обязательно принадлежат одной стране. Страны граничат, если они имеют соседние клетки. Изначально Кразилии принадлежит левая нижняя клетка карты, Хексике — правая верхняя. Гарантируется, что эти клетки входят в разные союзы.
После этого идёт целое число l — общее количество политических ходов, которые были сделаны (2 ≤ l ≤ 100). В следующей строке через пробел записаны l целых чисел от 0 до 9, обозначающих номера союзов, в которые вступала та или иная империя. Политические ходы империй упорядочены хронологически. Первый ход сделала Кразилия.

Результат

В первой строке выведите площадь территории Кразилии, во второй — Хексики.

Пример

исходные данныерезультат
6 12
000233434133
000233434143
001223434133
101023434143
101223434133
110233434143
4
0 4 2 1
23
18
Автор задачи: фольклор, подготовил Дмитрий Карпенко
Источник задачи: Уральская региональная командная олимпиада по программированию 2012