/*
Накратко перифразирано условие
В правоъгълна координатна система (N*N клетки, N<=10000) са разположени две
пръчки (RODS), една хоризонтална и една вертикална, всяка с дължина поне две
квадратчета и дебелина 1 квадратче. Двете пръчки може и да се застъпват.
Дадена е библиотечна функция, която проверява дали даден правоъгълен участък
застъпва част или цяла пръчка. Трябва с най-много 100 повиквания на функцията
да се определи местоположението и дължината на двете пръчки.

.......
.......
.....#.
.....#.
.###.#.
.....#.
.....#.
.......

Кратко описание на решението
Решаваме като извършим 6 двоични търсения. За всяко едно от тях извършваме
максимум 15 (lg 10000) операции. Броя на проверките в най-лошия случай достига
lg 10000 + 5 (за дадените тестове това достига 90 проверки).

Първите 4 двоични търсения извършваме за да ограничим пръчките отгоре, отдолу,
отляво и отдясно. След това проверяваме четирите ъглови квадратчета. В
зависимост от отговора на функцията имаме 10 възможни случая, които са описани
в сорс кода. Двете функции, с които извършваме двоичното търсене намират в
даден интервал къде е съответно най-горния (левия) и най-долния (десния) край
на пръчка.

findend(ffr,fto,c1,c2,h)

ffr и fto - начало и край
c1 и c2 - другите две координати
h : 0-двоичното търсене се извършва хоризонтално
    1-двоичното търсене се извършва вертикално
	
Веселин Райчев	
*/

// TO compile, add to linker options crectlib.o

#include <stdio.h>
#include "crectlib.h"

int check1(int x1,int y1,int x2,int y2)
{
  int r;
//  printf("c %d %d %d %d",x1+1,y1+1,x2,y2);
  r=rect(y1+1,y2,x1+1,x2);
//  printf(" = %d\n",r);
  return r?1:0;
}

int check(int ffr,int fto,int c1,int c2,int h)
{
  if (fto==ffr) { return 0; }

  if (h) { return check1(c1,ffr,c2,fto); }
  return check1(ffr,c1,fto,c2);
}

int findbeg(int ffr,int fto,int c1,int c2,int h)
{
  if (fto-ffr<=1)
  {
    if (check(ffr,fto,c1,c2,h)) { return ffr; }
    return fto;
  }
  {
    int m;
    m=(fto+ffr)/2;
    if (check(ffr,m,c1,c2,h)) { return findbeg(ffr,m,c1,c2,h); }
    return findbeg(m,fto,c1,c2,h);
//    if (check(m,fto,c1,c2,h)) { return findbeg(ffr,m,c1,c2,h); }
//    return findbeg(m,fto,c1,c2,h);
  }
}

int findend(int ffr,int fto,int c1,int c2,int h)
{
  if (fto-ffr<=1)
  {
    if (check(ffr,fto,c1,c2,h)) { return fto; }
    return ffr;
  }
  {
    int m;
    m=(ffr+fto)/2;
    if (check(m,fto,c1,c2,h)) { return findend(m,fto,c1,c2,h); }
    return findend(ffr,m,c1,c2,h);
  }
}

int decif(int a,int b)
{
  if (a==b) { return a-1; }
  return a;
}

int incif(int a,int b)
{
  if (a==b) { return a+1; }
  return a;
}

int rep(int hory,int horf,int hort,
        int verx,int verf,int vert)
{
  report(hory+1,horf+1,hory+1,hort,
         verf+1,verx+1,vert,verx+1);
  return 0;
}

int main(void)
{
  int x1,y1,x2,y2,n;
  
//  int hor,horf,hort;
//  int ver,verf,vert;

  n = gridsize();

  y1 = findbeg(0,n,0,n,1);  // === ffr,fto are in y
  y2 = findend(y1+2,n,0,n,1);

  x1 = findbeg(0,n,0,n,0);  // === ffr,fto are in x
  x2 = findend(x1+2,n,0,n,0);

//  printf("%d %d %d %d\n",x1,y1,x2,y2);

  switch (
    (check1(x1,y1,x1+1,y1+1)<<3) +
    (check1(x2-1,y1,x2,y1+1)<<2) +
    (check1(x1,y2-1,x1+1,y2)<<1) +
    (check1(x2-1,y2-1,x2,y2)   )  )
  {
    case 0: // + shape
            rep( findbeg(y1,y2,x1,x1+1,1) , x1,x2,
                 findbeg(x1,x2,y1,y1+1,0) , y1,y2); break;
    case 1:
    case 2: break; // impossible
    case 3: // _|_ shape
            rep( y2-1 , x1,x2 ,
                 findbeg(x1,x2,y1,y1+1,0) , y1,
                  incif( findend(y1,y2-1,x1,x2,1), y2-1)); break;
    case 4: break; // impossible
    case 5: // -| shape
            rep( findbeg(y1,y2,x1,x1+1,1) , x1,
                  incif( findend(x1,x2-1,y1,y2,0), x2-1),
                 x2-1 , y1,y2 ); break;
    case 6: if (check1(x2-2,y1,x2-1,y1+1))
            { // | ^
              rep( y1, findbeg(x1,x2,y1,y1+1,0) , x2 ,
                   x1, findbeg(y1,y2,x1,x1+1,1) , y2 );
            } else {
              rep( y2-1, x1, findend(x1,x2,y2-1,y2,0) ,
                   x2-1, y1, findend(y1,y2,x2-1,x2,1) );
            } break;
    case 7: // _| shape
              rep( y2-1, x1, incif(findend(x1,x2-1,y2-1,y2,0) , x2-1) ,
                   x2-1, y1, incif(findend(y1,y2-1,x2-1,x2,1) , y2-1) ); break;
    case 8: break; // impossible;
    case 9: if (check1(x1+1,y1,x1+2,y1+1))
            {
              rep( y1 , x1 , findend(x1,x2,y1,y1+1,0) ,
                   x2-1 , findbeg(y1,y2,x2-1,x2,1) , y2 );
            } else {
              rep( y2-1, findbeg(x1,x2,y2-1,y2,0) , x2 ,
                   x1 , y1 , findend(y1,y2,x1,x1+1,1) );
            } break;
   case 10: // |- shape
            rep( findbeg(y1,y2,x2-1,x2,1) ,
                  findbeg(x1+1,x2,y1,y2,0) , x2 ,
                 x1,y1,y2 ); break;
   case 11: // |_ shape
            rep( y2-1, decif( findbeg(x1+1,x2,y2-1,y2,0) , x1+1 ), x2 ,
                 x1, y1, incif( findend(y1,y2-1,x1,x1+1,1) ,y2-1) ); break;
   case 12: // ^|^ shape
            rep( y1,x1,x2,
                 findbeg(x1,x2,y2-1,y2,0) ,
                  decif( findbeg(y1+1,y2,x1,x2,1) , y1+1) , y2 ); break;
   case 13: // ^| shape
            rep( y1,x1, incif( findend(x1,x2-1,y1,y1+1,0) , x2-1 ),
                 x2-1, decif( findbeg(y1+1,y2,x2-1,x2,1) , y1+1 ) , y2 ); break;
   case 14: // |^ shape
            rep( y1,decif( findbeg(x1+1,x2,y1,y1+1,0) , x1+1) , x2 ,
                 x1,decif( findbeg(y1+1,y2,x1,x1+1,1) , y1+1) , y2 ); break;
   case 15: break; // impossible
    default: printf("Error\n"); // Internal error (should never happen)
  }

  return 0;
}