#include "locmin.h"

#include <algorithm>
#include <vector>
#include <cassert>

#include <iostream>

namespace Sol {
  template<class T> using vec = std::vector<T>;
  
  int query( int l, int c, bool transp ) { if( transp ) std::swap( l, c ); return ::value( l + 1, c + 1 ); }
  std::pair<int, int> sanitize( int x, int y, bool transp ) { if( transp ) std::swap( x, y ); return { x, y }; }

  std::pair<int, int> zile( int n, int m ) {
    int minx = 0, maxx = n - 1;
    int miny = 0, maxy = m - 1;
    bool transp = false;

    while( query( 0, 0, 0 ) );

    while( minx < maxx || miny < maxy ) {
      int lenx = maxx - minx + 1;
      int leny = maxy - miny + 1;

      if( lenx > leny ) {
	transp ^= 1;
	std::swap( minx, miny );
	std::swap( maxx, maxy );
	std::swap( lenx, leny );
      }

      // std::cout << minx << ' ' << maxx << " | " << miny << ", " << maxy << std::endl;

      assert( leny >= lenx );

      int mijy = (maxy + miny) / 2;
      vec<int> line(maxx - minx + 1);
      for( int x = minx; x <= maxx; x++ )
	line[x - minx] = query( x, mijy, transp );

      int bestx = std::min_element( line.begin(), line.end() ) - line.begin() + minx;

      if( miny < mijy && query( bestx, mijy - 1, transp ) < line[bestx - minx] ){
	maxy = mijy - 1;
	continue;
      }

      if( mijy < maxy && query( bestx, mijy + 1, transp ) < line[bestx - minx] ){
	miny = mijy + 1;
	continue;
      }

      return sanitize( bestx, mijy, transp );
    }

    return sanitize( minx, miny, transp );
  }
}

std::pair <int, int> find_locmin_point(int N, int M) {
  auto [a, b] = Sol::zile( N, M );
  return { a + 1, b + 1 };
}
  
