ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1923. Scary Politics

Time limit: 1.0 second
Memory limit: 64 MB
The world is in danger! Not so long ago the relations between two most powerful countries — Brazico and Mexil were merely cold, but now the world is on the brink of a new world war. Both Brazico and Mexil leaders are well-versed in politics, so before they declare war they try to acquire as many allies as possible.
In the beginning each country belonged to one of 10 alliances. Both rivaling empires do the same trick. The empire chooses one of the alliances (different from the one it belongs to in the moment) and joins it. As a result, all countries of the chosen alliance, that border on the empire become parts of the empire. As soon as the new territories are acquired, the leaders of the empire wait for their opponent to make a similar turn. Naturally, neither empire will join the alliance its rival is currently in. The alliances have quite different opinions on many things, so Brazico and Mexil can only be in one alliance at a time, but the territories they have once acquired remain parts of the empire forever, so each day makes their conflict more and more dangerous.
Fortunately, there is the political genius, who hasn’t pledged his service to any country yet. He is ready to propose a way to stop the war, but he needs to know exactly what the area of Brazico and Mexil are at the moment. You have the information on what alliances Brazico and Mexil joined during their political confrontation. Help to save the world — provide the political genius with information he requested.


The world map is a rectangle n × m, divided in 1 × 1 cells. In the first line are two numbers separated with white spaces: n and m — the size of the world map (2 ≤ n, m ≤ 50). Next n lines contain m digits each, describing the world map. For each cell the number from 0 to 9 denotes the alliance, this territory belongs to. All adjacent cells, belonging to one alliance form one country. The cells are called adjacent if they have common edge. Two countries border on each other, if they have at least a pair of adjacent cells. Initially Brazico is the country, containing the lower left cell, and the Mexill — the country containing upper right cell. It is given, that initially Brazico and Mexil belong to different alliances.
After that an integer l is given — a number of times the opposing empires joined different alliances (2 ≤ l ≤ 100). In the next n lines are integer numbers from 0 to 9, showing the number of alliance the corresponding empire joins. These numbers are given in chronological order, the first empire to join an alliance was Brazico.


In the first line print one integer number — the area of Brazico, in the second line — the area of Mexil.


6 12
0 4 2 1
Problem Author: folklore, prepared by Dmitry Karpenko
Problem Source: Ural Regional School Programming Contest 2012