#include "locmin.h"

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

#include <map>

namespace Sol {
  template<class T> using vec = std::vector<T>;
  using ll = long long;

  constexpr ll INF = 1e18 + 676767;
  
  ll query( int l, int c, bool transp ) {
    static std::map<std::pair<int, int>, ll> mem;
    if( transp ) std::swap( l, c );

    std::pair<int, int> x(l, c);
    if( mem.count( x ) ) return mem[x];
    return mem[x] = ::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;

    ll micutul = +INF, micx = -1, micy = -1;

    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::swap( micx, micy );
      }

      assert( leny >= lenx );

      int mijy = (maxy + miny) / 2;
      vec<ll> 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( line[bestx - minx] > micutul ){
	if( micy < mijy ){
	  maxy = mijy - 1;
	}else{
	  miny = mijy + 1;
	}
	continue;
      }

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

      if( mijy < maxy && (micutul = query( bestx, mijy + 1, transp )) < line[bestx - minx] ){
	miny = mijy + 1;
	micx = bestx;
	micy = 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 };
}
  
