/* POTM ENTRY : DVKha_DHTH_VN_Loser             */
/* Your Name : Dang Quang Linh                  */
/* Your email: VuongPhanTuan@YaHoo.com          */

/*  VietNamese . */
/*  Version 4.0 ! New version ! */
/*  Thank you very much ! I am very happy when my program run on          */
/*  your machine                                                          */
/*  I was compile it by GCC 2.7.2.1 (on MS-DOS , PC Pentium 166 MMX)      */

/* Compile : GCC <file>                                                   */

/*  My algorithm : First , I use DIJKSTRA algorithm to find shortest road */
/*  from (0,0) to (size-1,size-1) . After that , I use greedy method to   */
/*  find longest road from (size-1,size-1) to (0,0)                       */

#include <stdio.h>
#include <stdlib.h>

/*#define DEBUG 0*/

int my_rand(int xx);

#define MaxN 262
#define CountS 7
#define TIMEALL 540                     /* Time run */
#define Infinite 1000000000

int m,n,maxmove,maxhigh,mov1,mov2,move,u,v,MaxS,stop;
long road1,road2,distance,best;
unsigned int a[MaxN][MaxN];             /* Altitude grid */
FILE *f;

/* This is my check time from POTM timecode.htm */
#ifdef __BORLANDC__
#include <time.h>	/* for the time_t structure */

time_t	Started;

int timeout() {
	time_t	Current;

	time(&Current);
	if (difftime(Current, Started) > TIMEALL) return 1; else return 0;
}
#else

#include <sys/times.h>	/* for the TMS structure */
#define CLK_TCK 100	/* Note: this may be different on YOUR box, you
			   might find the value of HZ in YOUR param.h, but
			   it's gotta be 100 when you ship your entry!
			   Alternatively, use sysconf to deduce CLK_TCK -
			   this approach should work on both systems!	*/
int timeout()
{
	int seconds;
	static struct tms TMS;
	times(&TMS);
	/* add the elapsed system and user times 			*/
	/* calculation comes out to the nearest second - rounded down 	*/
	seconds = (TMS.tms_stime + TMS.tms_utime)/CLK_TCK ;

	if (seconds >= TIMEALL) return 1; else return 0;
}
#endif

int dx[9] = { 0, 1, 1, 1, 0, 0,-1,-1,-1};
int dy[9] = { 0, 1, 0,-1, 1,-1, 1, 0,-1};

unsigned char mark[MaxN][MaxN];
unsigned char pre[MaxN][MaxN];
unsigned char p1[MaxN][MaxN],p2[MaxN][MaxN],bp[MaxN][MaxN];
long ist[MaxN][MaxN];
unsigned char qx[MaxN*MaxN],qy[MaxN*MaxN],sx[MaxN*MaxN],sy[MaxN*MaxN];
unsigned int step[MaxN][MaxN];

int max2(int a,int b)
{
  return ( (a > b) ? a : b);
}

void readdata(char *name)
{
  int i,j;

  f = fopen(name,"r");
  if (f==NULL) {
    printf(" File input not found ");
    exit(0);
  }
  fscanf(f,"P2\n# %d\n%d %d\n%d\n",&maxmove,&n,&m,&maxhigh);
  for (i=1;i<=m;i++)
    for (j=1;j<=n;j++) fscanf(f,"%d",&a[i][j]);
  fclose(f);
}

void wall()
{
  int i,j;

  for (i=0;i<=m+1;i++) {
    mark[i][0] = 1;mark[i][n+1] = 1;
  }
  for (j=0;j<=n+1;j++) {
    mark[0][j] = 1;mark[m+1][j] = 1;
  }
  for (i=1;i<=m;i++)
    for (j=1;j<=n;j++) mark[i][j] = 0;
}

void prepare()
{
  int i,j;

  for (i=0;i<=m+1;i++) {
    p1[i][0] = 1;p1[i][n+1] = 1;
  }
  for (j=0;j<=n+1;j++) {
    p1[0][j] = 1;p1[m+1][j] = 1;
  }
  for (i=0;i<=m+1;i++)
    for (j=0;j<=n+1;j++) step[i][j] = 0;
}

/* procedure go1() : is DIJKSTRA algorithm to find shortest from (0,0) */
/* to (size-1,size-1)                                                  */

void go1()
{
  unsigned int i,j,count,x,y,u,v,mini,maxm;
  long min;

  maxm = (maxmove/10)*4;
  for (i=1;i<=m;i++)
    for (j=1;j<=n;j++) pre[i][j] = 0;
  for (i=1;i<=m;i++)
    for (j=1;j<=n;j++) ist[i][j] = Infinite;
  mark[m][n] = 1;ist[m][n] = 0;step[m][n] = 0;
  count = 0;x = m;y = n;
  while (mark[1][1]==0) {
    for (i=1;i<=8;i++) {
      u = x+dx[i];v = y+dy[i];
      if (mark[u][v]==0&&step[x][y]+1+max2(u,v)<= maxm)
	if (ist[x][y]+abs(a[x][y]-a[u][v])<ist[u][v]) {
	  ist[u][v] = ist[x][y]+abs(a[x][y]-a[u][v]);
	  if (pre[u][v]==0) {
	    count ++;qx[count] = u;qy[count] = v;
	  }
	  pre[u][v] = i;step[u][v] = step[x][y]+1;
	}
    }
    min = Infinite;
    for (i=1;i<=count;i++) {
      x = qx[i];y = qy[i];
      if (ist[x][y]<min) {
	min = ist[x][y];mini = i;
      }
    }
    if (min>road1) return;
    x = qx[mini];y = qy[mini];
    qx[mini] = qx[count];qy[mini] = qy[count];count --;
    mark[x][y] = 1;
  }
  pre[m][n] = 0;
  if (ist[1][1]<road1) {
    road1 = ist[1][1];mov1 = step[1][1];
    for (i=1;i<=m;i++)
      for (j=1;j<=n;j++) p1[i][j] = 0;
    x = 1;y = 1;
    while (pre[x][y]!=0) {
      i = pre[x][y];
      p1[x][y] = i;
      x -= dx[i];y -= dy[i];
    }
  }
}

void update(x,y)
  int x,y;
{
  int i;

  pre[u][v] = 0;move += step[x][y];road2 += ist[x][y];
  u = x;v = y;
  while (pre[x][y]!=0) {
    i = pre[x][y];
    p2[x][y] = i;
    x -= dx[i];y -= dy[i];
  }
}

void seek()
{
  int i,j,count1,count2,x,y,s,t,amount,maxi,number;
  unsigned char rx[CountS+10],ry[CountS+10];
  long max;

  for (i=0;i<=m+1;i++)
    memcpy(pre[i],p2[i],(n+2)*sizeof(p2[1][1]));
  for (i=1;i<=m;i++)
    for (j=1;j<=n;j++) step[i][j] = 30000;
  for (i=1;i<=m;i++)
    for (j=1;j<=n;j++) ist[i][j] = -1;
  count1 = 1;qx[count1] = u;qy[count1] = v;
  step[u][v] = 0;ist[u][v] = 0;amount = 0;number = 0;
  pre[m][n] = 1;
  while (count1>0) {
    count2 = 0;number ++;
    for (i=1;i<=count1;i++) {
      x = qx[i];y = qy[i];
      if (ist[x][y]>=distance) {
	amount = 1;break;
      }
      for (j=1;j<=8;j++) {
	s = x+dx[j];t = y+dy[j];
	if (step[s][t]>=number&&move+step[x][y]+1+max2(m-s,n-t)<=mov2)
	  if (ist[x][y]+abs(a[x][y]-a[s][t])>ist[s][t]) {
	    ist[s][t] = ist[x][y]+abs(a[x][y]-a[s][t]);
	    if (pre[s][t] == 0) {
	      count2++;sx[count2] = s;sy[count2] = t;
	    }
	    pre[s][t] = j;step[s][t] = step[x][y]+1;
	  }
      }
    }
    if (amount>=1) break;
    memcpy(qx,sx,(count2+1)*sizeof(sx[1]));
    memcpy(qy,sy,(count2+1)*sizeof(sy[1]));
    count1 = count2;
  }
  amount = 0;
  for (i=1;i<=count1;i++) {
    max = 0;
    for (j=i;j<=count1;j++) if (ist[qx[j]][qy[j]]>max) {
      max = ist[qx[j]][qy[j]];maxi = j;
    }
    if (max>=distance&&amount<MaxS) {
      amount ++;rx[amount] = qx[maxi];ry[amount] = qy[maxi];
    } else break;
    qx[maxi] = qx[i];qy[maxi] = qy[i];
  }
  if (amount > 0) {
    i = my_rand(i) % amount + 1;
    update(rx[i],ry[i]);
  } else {
    if (ist[m][n]>0) update(m,n);stop = 1;
  }
}

int good(int x1,int y1,int x2,int y2)
{
  if (abs(x1-x2)>1||abs(y1-y2)>1) return 0;
  if (abs(x1-x2)==0&&abs(y1-y2)==0) return 0;
  return 1;
}

int change(int x1,int y1,int x2,int y2)
{
  int i;

  for (i=1;i<=8;i++)
    if (x1+dx[i]==x2&&y1+dy[i]==y2) return i;
  return 0;
}

void more()
{
  int x,y,i,j,u,v;
  x = m;y = n;
  while ((x!=1||y!=1)&&move<mov2) {
    i = p2[x][y];
    for (j=1;j<=8;j++) {
      u = x-dx[j];v = y-dy[j];
      if (p2[u][v]==0&&good(u,v,x-dx[i],y-dy[i])==1) {
	p2[x][y] = j;p2[u][v] = change(x-dx[i],y-dy[i],u,v);
	road2 = road2 - abs(a[x][y]-a[x-dx[i]][y-dy[i]])
		+ abs(a[x][y]-a[u][v])+ abs(a[u][v]-a[x-dx[i]][y-dy[i]]);
	move ++;
	break;
      }
    }
    i = p2[x][y];
    x = x-dx[i];y = y-dy[i];
  }
}

/*  procedure better() : road longer by change the point in road */

void better()
{
  int x,y,i,j,u,v,s,t,p,q,found,count;

  if (move<mov2) more();
  found = 1;count = 0;
  while (found==1) {
    x = m;y =n;u = m;v = n;found = 0;
    while (s!=1||t!=1) {
      i = p2[x][y];
      u = x-dx[i];v =y-dy[i];
      j = p2[u][v];
      s = u-dx[j];t = v-dy[j];
      for (i=1;i<=8;i++) {
	p = x+dx[i];q = y+dy[i];
	if (p2[p][q] == 0&&good(x,y,p,q)==1&&good(p,q,s,t)==1)
	  if (abs(a[x][y]-a[u][v])+abs(a[u][v]-a[s][t])<abs(a[x][y]-a[p][q])+abs(a[p][q]-a[s][t])) {
	    p2[u][v] = 0;found = 1;
	    road2 = road2-abs(a[x][y]-a[u][v])-abs(a[u][v]-a[s][t])+abs(a[x][y]-a[p][q])+abs(a[p][q]-a[s][t]);
	    u = p;v = q;
	    p2[x][y] = change(u,v,x,y);
	    p2[u][v] = change(s,t,u,v);
	  }
      }
      i = p2[x][y];
      x = x-dx[i];y =y-dy[i];
      count ++;
      if (count>200)
	return;
    }
  }
}

void init()
{
  int i;

  move = 0;u = 1; v = 1;road2 = 0;stop = 0;
  for (i=0;i<=m+1;i++)
    memcpy(p2[i],p1[i],(n+2)*sizeof(p1[1][1]));
  do {
    seek();
  } while (stop==0&&timeout()==0);
  if (road2+100>best&&p2[m][n]!=0)
     better();
}

/* procedure go2() : greedy method */

void go2()
{
  int i;

  best = 0;
  do {
    init();
    if (road2>best&&p2[m][n]!=0) {
      best = road2;
      for (i=0;i<=m+1;i++)
	memcpy(bp[i],p2[i],(n+2)*sizeof(p2[1][1]));
      #ifdef DEBUG
	printf("%f %ld\n",(float)road2/(float)road1,road2);
      #endif
    }
    if (best!=0) distance = best/(20+my_rand(distance) % 9);
    if (MaxS==CountS) MaxS=2 ; else MaxS=CountS;
  } while (timeout()==0);
}

void thinking()
{
  int i,j;

  road1 = Infinite;

  wall();
  for (i=1;i<=m-1;i++) mark[i][n] = 1;
  for (j=2;j<=n;j++) mark[1][j] = 1;
  go1();

  wall();
  for (i=2;i<=m;i++) mark[i][1] = 1;
  for (j=1;j<=n-1;j++) mark[m][j] = 1;
  go1();

  mov2 = maxmove-mov1;
  distance = (mov2*50)/20;
  MaxS = CountS;
  go2();
}

void result()
{
  int x,y,i;

  x = 1-dx[bp[1][1]];y =1-dy[bp[1][1]];
  bp[1][1] = 0;
  while (bp[x][y]!=0) {
    printf("%d %d\n",x-1,y-1);
    i = bp[x][y];
    x = x-dx[i];y = y-dy[i];
  }
  printf("%d %d\n",x-1,y-1);
}

void main(int argc,char **argv)
{
#ifdef __BORLANDC__
  time(&Started);
#endif
  readdata(argv[1]);
  prepare();
  thinking();
  result();
#ifdef DEBUG
  printf("%f\n",(float)best/(float)road1);
#endif
}

/* ----------------------- rand() ---------------------- */
/*      I write a new random procedure for my program    */

unsigned int cxx=0,bxx=1;

#define xc(a,b)         \
     i = a;a = b; b =i; \

#define ad(a,b)         \
     a = (a+b) & 0xFFFF ;          \

#define ml(k)                 \
     dxx = (axx*k) >> 16    ; \
     axx = (axx*k) & 0xFFFF       ; \

int my_rand(int xx)
{
  unsigned long axx=0x4E35,dxx=0x015A,sii=xx,i;
  unsigned long k;

    xc(sii,axx);
    xc(dxx,axx);
    if (axx!=0) {
      ml(bxx);
    }
    if (cxx!=0) {
      xc(cxx,axx);
      ml(sii);
      ad(axx,cxx);
    }
    xc(sii,axx);
    ml(bxx);
    ad(dxx,sii);
  k = (dxx << 16) + axx + 1;
  bxx = k & 0xFFFF;cxx = k >> 16;
  return (cxx & 0x7FFF);
}
/* ----------------------- rand() ---------------------- */