using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3 3 5");
WillReturn.Add("10 2 10");
WillReturn.Add("3 1 4");
WillReturn.Add("10 5 10");
//9
//7
//6
//5
//4
}
else if (InputPattern == "Input2") {
WillReturn.Add("3 5 3");
WillReturn.Add("2 2 3 3 3");
WillReturn.Add("2 1 2 1 3");
WillReturn.Add("2 2 3 3 3");
//15
//7
//0
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
long TotalYear = wkArr[2];
long[,] BanArr = CreateBanArr(InputList.Skip(1));
long UB_X = BanArr.GetUpperBound(0);
long UB_Y = BanArr.GetUpperBound(1);
var InsPQueue = new PQueue_Arr();
PQueue_Arr.PQueueJyoutaiDef WillEnqueue;
var VisitedPosSet = new HashSet<long>();
// 外周をPQueueにInsert
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
if (Y == 0 || Y == UB_Y || X == 0 || X == UB_X) {
WillEnqueue.Val = BanArr[X, Y];
WillEnqueue.X = X;
WillEnqueue.Y = Y;
InsPQueue.Enqueue(WillEnqueue);
VisitedPosSet.Add(GetHash(X, Y));
}
}
}
long CurrYear = 0;
long SinkCnt = 0;
while (InsPQueue.Count() > 0) {
PQueue_Arr.PQueueJyoutaiDef Dequeued = InsPQueue.Dequeue();
CurrYear = Math.Max(CurrYear, Dequeued.Val);
long Hash = GetHash(Dequeued.X, Dequeued.Y);
VisitedPosSet.Add(Hash);
AnswerDef WillAdd;
WillAdd.Year = CurrYear;
WillAdd.SinkCnt = ++SinkCnt;
mAnswerList.Add(WillAdd);
Action<long, long> EnqueueAct = (pX, pY) =>
{
if (pX < 0 || UB_X < pX) return;
if (pY < 0 || UB_Y < pY) return;
long CurrHash = GetHash(pX, pY);
if (VisitedPosSet.Add(CurrHash)) {
WillEnqueue.X = pX;
WillEnqueue.Y = pY;
WillEnqueue.Val = BanArr[pX, pY];
InsPQueue.Enqueue(WillEnqueue);
}
};
EnqueueAct(Dequeued.X, Dequeued.Y - 1);
EnqueueAct(Dequeued.X, Dequeued.Y + 1);
EnqueueAct(Dequeued.X - 1, Dequeued.Y);
EnqueueAct(Dequeued.X + 1, Dequeued.Y);
}
Dictionary<long, long> ResultDict = mAnswerList.GroupBy(pX => pX.Year).
ToDictionary(pX => pX.Key, pX => pX.Max(Item => Item.SinkCnt));
var sb = new System.Text.StringBuilder();
long AllShimaCnt = (UB_X + 1) * (UB_Y + 1);
long CurrShimaCnt = AllShimaCnt;
for (long I = 1; I <= TotalYear; I++) {
if (ResultDict.ContainsKey(I)) {
CurrShimaCnt = AllShimaCnt - ResultDict[I];
}
sb.Append(CurrShimaCnt);
sb.AppendLine();
}
Console.Write(sb.ToString());
}
struct AnswerDef
{
internal long Year;
internal long SinkCnt;
}
static List<AnswerDef> mAnswerList = new List<AnswerDef>();
////////////////////////////////////////////////////////////////
// IEnumerable<string>をlongの2次元配列に設定する
////////////////////////////////////////////////////////////////
static long[,] CreateBanArr(IEnumerable<string> pStrEnum)
{
var StrList = pStrEnum.ToList();
if (StrList.Count == 0) {
return new long[0, 0];
}
long[] IntArr = { };
Action<string> SplitAct = pStr =>
IntArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
SplitAct(StrList[0]);
long UB_X = IntArr.GetUpperBound(0);
long UB_Y = StrList.Count - 1;
long[,] WillReturn = new long[UB_X + 1, UB_Y + 1];
for (long Y = 0; Y <= UB_Y; Y++) {
SplitAct(StrList[(int)Y]);
for (long X = 0; X <= UB_X; X++) {
WillReturn[X, Y] = IntArr[X];
}
}
return WillReturn;
}
static long GetHash(long pX, long pY)
{
return pX * 10000 + pY;
}
}
#region PQueue_Arr
// 内部で配列使用の優先度付きキュー (根のValが最小)
internal class PQueue_Arr
{
internal struct PQueueJyoutaiDef
{
internal long Val;
internal long X;
internal long Y;
}
private PQueueJyoutaiDef[] mHeapArr;
private long mHeapArrCnt = 0;
// コンストラクタ
internal PQueue_Arr()
{
mHeapArr = new PQueueJyoutaiDef[65535];
}
internal bool IsEmpty()
{
return mHeapArrCnt == 0;
}
internal long Count()
{
return mHeapArrCnt;
}
internal long Peek()
{
return mHeapArr[1].Val;
}
// エンキュー処理
internal void Enqueue(PQueueJyoutaiDef pAddJyoutai)
{
long CurrNode = 1 + mHeapArrCnt;
if (mHeapArr.GetUpperBound(0) < CurrNode) {
ExtendArr();
}
mHeapArr[CurrNode] = pAddJyoutai;
mHeapArrCnt++;
while (1 < CurrNode && mHeapArr[CurrNode / 2].Val > mHeapArr[CurrNode].Val) {
PQueueJyoutaiDef Swap = mHeapArr[CurrNode];
mHeapArr[CurrNode] = mHeapArr[CurrNode / 2];
mHeapArr[CurrNode / 2] = Swap;
CurrNode /= 2;
}
}
// 配列のExtend
private void ExtendArr()
{
PQueueJyoutaiDef[] NewHeapArr = new PQueueJyoutaiDef[mHeapArrCnt * 2];
mHeapArr.CopyTo(NewHeapArr, 0);
mHeapArr = NewHeapArr;
}
// デキュー処理
internal PQueueJyoutaiDef Dequeue()
{
PQueueJyoutaiDef TopNode = mHeapArr[1];
long LastNode = mHeapArrCnt;
mHeapArr[1] = mHeapArr[LastNode];
mHeapArrCnt--;
MinHeapify(1);
return TopNode;
}
// 根ノードを指定し、根から葉へヒープ構築
private void MinHeapify(long pRootNode)
{
if (mHeapArrCnt <= 1) {
return;
}
long Left = pRootNode * 2;
long Right = pRootNode * 2 + 1;
// 左の子、自分、右の子で値が最小のノードを選ぶ
long Smallest = mHeapArr[pRootNode].Val;
long SmallestNode = pRootNode;
if (Left <= mHeapArrCnt && mHeapArr[Left].Val < Smallest) {
Smallest = mHeapArr[Left].Val;
SmallestNode = Left;
}
if (Right <= mHeapArrCnt && mHeapArr[Right].Val < Smallest) {
Smallest = mHeapArr[Right].Val;
SmallestNode = Right;
}
// 子ノードのほうが小さい場合
if (SmallestNode != pRootNode) {
PQueueJyoutaiDef Swap = mHeapArr[SmallestNode];
mHeapArr[SmallestNode] = mHeapArr[pRootNode];
mHeapArr[pRootNode] = Swap;
// 再帰的に呼び出し
MinHeapify(SmallestNode);
}
}
}
#endregion