Карты в игре разбиты на квадратные ячейки, которые называются гео-панелями. Некоторые из этих панелей окрашены. Будем считать, что гео-панели, которые не имеют цвета, покрашены в прозрачный цвет.
Еще на карте есть так называемые гео-символы. Они имеют вид цветных пирамидок (в том числе существуют гео-символы прозрачного цвета). Каждый гео-символ расположен на одной гео-панели, а на каждой гео-панели может находиться не более одного гео-символа.
Гео-символы можно уничтожать. Чтобы лучше понять что происходит при уничтожении гео-символов, заведем некую очередь, в которую будем складывать только что уничтоженные гео-символы.
В самом начале поместим в очередь только что уничтоженный гео-символ. Далее будем повторять следующую операцию:
Извлечем из начала очереди гео-символ. Посмотрим на цвет панели, на которой находился данный гео-символ. Если он отличен от прозрачного и отличен от цвета данного гео-символа, то происходит перекрашивание всех гео-панелей этого цвета в цвет данного гео-символ (в том числе, прозрачные гео-символы перекрашивают гео-панели в прозрачный цвет). Перекрашивание происходит по бесконечной спирали строго в следующем порядке, начиная от панели, на которой стоял гео-символ:
Другими словами, мы выбираем все панели, которые нужно перекрасить и находим их номера в бесконечной спирали, центр которой помещен в позицию данного гео-символа. После этого перекрашиваем их в порядке возрастания номеров.
Если в момент перекрашивания панели на ней находится еще один гео-символ, то он удаляется с карты и помещается в конец очереди.
После перекрашивания гео-символ уничтожается окончательно и из начала очереди извлекается следующий гео-символ (если он есть) и процесс повторяется. Процесс заканчивается если очередь оказалась пуста.
Чтобы лучше понять этот процесс — смотрите разбор примера.
Вам известны цвета всех гео-панелей и расположение всех гео-символов. Определите количество перекрашиваний, которое случится, если уничтожить один из гео-символов.
Выходные данные
Выведите одно целое число — общее количество перекрашиваний после уничтожения гео-символа.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cout (также вы можете использовать спецификатор %I64d).
Примечание
Все действия, происходящие в примере можно видеть на следующей картинке:
Если ваш браузер не поддерживает APNG, и вы видите только статичную картинку, то вы можете посмотреть GIF версию этой картинки по следующей ссылке:
105_D_img_2.gif