eliberare

#include <fstream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

ifstream fin("eliberare.in");
ofstream fout("eliberare.out");

int N, M;

int main() {
    fin >> N >> M;
    vector<string> g(N);
    for (int i = 0; i < N; i++) fin >> g[i];
    auto id = [&](int i, int j) { return i * M + j; };

    vector<int> L(N * M), R(N * M), U(N * M), D(N * M); // vecini pe rând/coloană (-1 = niciunul)
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {
        int k = id(i, j);
        L[k] = j > 0 ? id(i, j - 1) : -1;
        R[k] = j < M - 1 ? id(i, j + 1) : -1;
        U[k] = i > 0 ? id(i - 1, j) : -1;
        D[k] = i < N - 1 ? id(i + 1, j) : -1;
    }
    vector<char> gone(N * M, 0), inq(N * M, 0);
    auto rel = [&](int k) { char d = g[k / M][k % M];
        if (d == '>') return R[k] == -1;
        if (d == '<') return L[k] == -1;
        if (d == '^') return U[k] == -1;
        return D[k] == -1;
    };
    queue<int> q;
    for (int k = 0; k < N * M; k++) if (rel(k)) { q.push(k); inq[k] = 1; }

    while (!q.empty()) {
        int k = q.front(); q.pop();
        if (gone[k]) continue;
        gone[k] = 1;
        fout << k / M + 1 << " " << k % M + 1 << "\n";
        int l = L[k], r = R[k], u = U[k], d = D[k];
        if (l != -1) R[l] = r;
        if (r != -1) L[r] = l;
        if (u != -1) D[u] = d;
        if (d != -1) U[d] = u;
        for (int nb : {l, r, u, d})
            if (nb != -1 && !gone[nb] && !inq[nb] && rel(nb)) { inq[nb] = 1; q.push(nb); }
    }
    return 0;
}