/*****/ #define TRUE true #define FALSE false #include /**/ #pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") /**/ using namespace std; using ll = long long; using ld = long double; using pint = pair; using pll = pair; template using vec = vector; template using vec2 = vector>; template using vec3 = vector>>; constexpr int INF = numeric_limits::max(); constexpr ll INFL = numeric_limits::max(); constexpr ll MOD = 1000000007; // 10^9+7 #ifdef TRUE #define rep(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i) #define rep1(i, n) for (ll i = 1, i##_len = (n); i <= i##_len; ++i) #define rrep(i, n) for (ll i = (n)-1; i >= 0; --i) #define rrep1(i, n) for (ll i = (n); i > 0; --i) #define step(i, a, n) for (ll i = (a), i##_len = (a) + (n); i < i##_len; ++i) #define rstep(i, a, n) for (ll i = (a) + (n)-1, i##_len = (a); i >= i##_len; --i) #define range(i, a, b) for (ll i = (a), i##_len = (b); i < i##_len; ++i) #define rrange(i, a, b) for (ll i = (b)-1, i##_len = (a); i >= i##_len; --i) std::string strMulti(const int n, const std::string &t) { std::string out = ""; for (int i = 0; i < n; i++) { out += t; } return out; } std::string tab(const int n) { return string(n, '\t'); } std::string join(const vector &v, const char *delim = 0) { std::string s; if (!v.empty()) { s += v[0]; for (decltype(v.size()) i = 1, c = v.size(); i < c; ++i) { if (delim) s += delim; s += v[i]; } } return s; } string to_string(string &s) { return '"' + s + '"'; } string to_string(char &c) { return string({'\'', c, '\''}); } template string to_string(pair p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template string _to_string_tuple(Tuple &&t, std::index_sequence) { return "(" + join({to_string(std::get(t))...}, ", ") + ")"; } template string to_string(tuple t) { return _to_string_tuple(std::forward>(t), std::make_index_sequence>>::value>{}); } template string to_string(vector ar) { vector texts(ar.size()); for (size_t i = 0; i < ar.size(); ++i) { texts[i] = to_string(ar[i]); } return "{" + join(texts, ", ") + "}"; } template string to_string(set se) { vector texts(se.size()); size_t i = 0; for (auto v : se) { texts[i] = to_string(v); ++i; } return "{" + join(texts, ", ") + "}"; } template string to_string(initializer_list il) { vector texts(il.size()); size_t i = 0; for (T v : il) { texts[i] = to_string(v); i++; } return "{" + join(texts, ", ") + "}"; } void debug(string name); void debugn(string name); template void debug(string name, T v); template void debugn(string name, T v); template void debug(string name, initializer_list il); template void debugn(string name, initializer_list il); template void debug(string name, Args... args); template void debugn(string name, Args... args); void debugdo(function func); #ifdef DEBUG_BUILD #define debugvar(x) debugn(#x, (x)) #define debugvartab(x, t) debugn(tab(t) + #x, (x)) void debug(string name) { std::cerr << name; } void debugn(string name) { std::cerr << name << '\n'; } template void debug(string name, T v) { std::cerr << name << " = " << to_string(v); } template void debugn(string name, T v) { std::cerr << name << " = " << to_string(v) << '\n'; } template void debug(string name, initializer_list il) { std::cerr << name << " = " << to_string(il); } template void debugn(string name, initializer_list il) { std::cerr << name << " = " << to_string(il) << '\n'; } template void debug(string name, Args... args) { std::cerr << name << " = " << to_string(tuple(args...)); } template void debugn(string name, Args... args) { std::cerr << name << " = " << to_string(tuple(args...)) << '\n'; } void debugdo(function func) { func(); } #else #define debugvar(x) #define debugvartab(x, t) void debug(string name) { } void debugn(string name) {} template void debug(string name, T v) {} template void debugn(string name, T v) {} template void debug(string name, initializer_list il) {} template void debugn(string name, initializer_list il) {} template void debug(string name, Args... args) {} template void debugn(string name, Args... args) {} void debugdo(function func) {} #endif #define all(x) (x).begin(), (x).end() #define pair(a, b) make_pair(a, b) template bool chmax(T &a, const T b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T &a, const T b) { if (a > b) { a = b; return true; } return false; } template T divup(const T a, const T b) { if (a % b == 0) { return a / b; } return a / b + 1; } template bool cmp_2nd(pair a, pair b) { if (a.second != b.second) { return a.second < b.second; } return a.first < b.first; } ll modpow(ll x, ll n, const ll &p) { ll ret = 1; while (n > 0) { if (n & 1) { (ret *= x) %= p; } (x *= x) %= p; n >>= 1; } return ret; } template T modinv(T a, const T &p) { T b = p, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= p; if (u < 0) { u += p; } return u; } template T math_P(T m, T n) { T ret = 1; for (T i = m; i > m - n; i--) { ret *= i; } return ret; } template T math_C(T m, T n) { T ret = math_P(m, n); for (T i = 2; i <= n; i++) { ret /= i; } return ret; } ll extended_euclidean(ll u, ll v) { ll r0 = u; ll r1 = v; ll s0 = 1; ll s1 = 0; ll t0 = 0; ll t1 = 1; while (r1 != 0) { ll q = r0 / r1; ll r = r0 - q * r1; ll s = s0 - q * s1; ll t = t0 - q * t1; r0 = r1; s0 = s1; t0 = t1; r1 = r; s1 = s; t1 = t; } if (t0 < 0) { return t0 + u; } else { return t0; } } ll math_C_mod(ll n, ll c, const ll &p) { ll upe = 1; ll dow = 1; for (ll i = 1; i < c + 1; ++i) { upe = upe * n % p; dow = dow * i % p; n -= 1; } return (upe * extended_euclidean(p, dow)) % p; } template T math_gcd(T a, T b) { if (b == 0) { return a; } else { return math_gcd(b, a % b); } } template T math_lcm(T a, T b) { return a / math_gcd(a, b) * b; } template T SumStep(T a, T n, T d) { return n * (2 * a + (n - 1) * d) / 2; } template T SumRange(T a, T b, T d) { return SumStep(a, (b - a) / d, d); } #endif /*****/ class Point { public: int x = 0; int y = 0; Point() = default; Point(int x, int y) { set(x, y); } Point(const Point &p) { set(p.x, p.y); } void set(int _x, int _y) { x = _x; y = _y; } void move(int dx, int dy) { x += dx; y += dy; } inline Point up1() const { return Point(x, y + 1); } inline Point down1() const { return Point(x, y - 1); } inline Point right1() const { return Point(x + 1, y); } inline Point left1() const { return Point(x - 1, y); } inline array adjoin() const { return { this->up1(), this->down1(), this->right1(), this->left1(), }; } inline bool isWithin(int w, int h) const { return 0 <= x && x < w && 0 <= y && y < h; } }; string to_string(Point p) { return "(" + to_string(p.x) + ", " + to_string(p.y) + ")"; } void Main() { int W, H; cin >> W >> H; vec2 M(H, vec(W)); rep(y, H) rep(x, W) cin >> M[y][x]; bool ret = false; rep1(m, 1000) { debugvar(m); vec2 seen(H, vec(W)); queue> que; int beginY = 0; while (beginY < H) { debugvartab(beginY, 1); bool isBreak = false; rep(x, W) { if (!seen[beginY][x] && M[beginY][x] == m) { que.push(pair(Point(x, beginY), Point(-100, -100))); isBreak = true; break; } } if (!isBreak) { beginY++; } while (!que.empty()) { Point now = que.front().first; Point back = que.front().second; debugvartab(now, 2); debugvartab(back, 3); que.pop(); seen[now.y][now.x] = true; for (Point to : now.adjoin()) { if (to.isWithin(W, H) && M[to.y][to.x] == m) { //debugvartab(to, 3); //debugvartab(seen[to.y][to.x], 4); if (to.x != back.x || to.y != back.y) { if (seen[to.y][to.x]) { ret = true; } else { seen[to.y][to.x] = true; que.push(pair(to, now)); } } } } } } } cout << (ret ? "possible" : "impossible") << endl; } /*****/ int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout << std::fixed << std::setprecision(10); Main(); std::cerr << flush; std::cout << flush; return 0; }