## 1) Abridged problem statement

You are given an \(R \times C\) grid (\(1 \le R,C \le 30\)).  
Each cell contains:
- a lowercase letter
- an arrow (`<`, `>`, `^`, `v`) pointing to a neighboring cell (or off the grid)

Starting from any cell, you repeatedly:
1. write down the current cell’s letter
2. move to the neighbor indicated by the arrow  
If you step outside the grid, the process stops.

For each of \(Q \le 50\) queries, a word is given in **compressed form**: fragments like `(F)K` mean repeat string `F` exactly `K` times. Parentheses do **not** nest. Decompressed length \(\le 10^9\).

For each query, output:
- `YES (X,Y)` with the lexicographically smallest start cell (min row, then min col) from which the exact word is read, or
- `NO` if impossible.

---

## 2) Detailed editorial (solution explanation)

### Key observations

1. The grid defines a **functional graph**: from each cell there is exactly one outgoing edge (to the next cell or “outside”).  
   Therefore, for a chosen start cell, the read word is exactly the sequence of letters along that unique path.

2. Query strings can be up to \(10^9\) when decompressed, so we cannot build them explicitly.

3. We only have at most \(900\) start positions, and at most \(50\) queries.  
   If for each start cell we can compute a **hash** of the first \(L\) letters on its path in \(O(\log L)\), then checking all cells is feasible:
   \[
   900 \cdot 50 \cdot \log(10^9) \approx 900 \cdot 50 \cdot 30 \;\text{operations}
   \]

So the problem splits into two parts:

- Compute the hash (and length) of each query (from compressed form) without decompressing.
- For each cell, compute the hash of the first `len(query)` letters along its arrow-walk quickly.

We use **polynomial rolling hash** modulo \(2^{61}-1\) (fast, low collision risk), and **binary lifting** on the grid paths.

---

### Hash representation and concatenation

Let a string \(S = s_0 s_1 \dots s_{n-1}\). Define hash:
\[
H(S) = (((s_0)\cdot B + s_1)\cdot B + \dots )\cdot B + s_{n-1}
\]
Also store \(P(S)=B^{|S|}\). Then concatenation is easy:

If we have monoids:
- \(A = (H(A), P(A), |A|)\)
- \(B = (H(B), P(B), |B|)\)

Then
\[
H(A+B) = H(A)\cdot P(B) + H(B), \quad P(A+B)=P(A)\cdot P(B), \quad |A+B|=|A|+|B|
\]

The code wraps this in `HashMonoid` with `merge()`.

---

### Part A: Binary lifting over the grid (to hash a path prefix)

For each cell `(i,j)`, define:
- `jump[l][i][j]` = the cell reached after \(2^l\) arrow moves (or `(-1,-1)` if it goes outside before that)
- `dp[l][i][j]` = `HashMonoid` of the string of letters read over the next \(2^l\) moves starting at `(i,j)`  
  (i.e., the letters of the first \(2^l\) visited cells)

Base case \(l=0\):
- `jump[0]` is the immediate neighbor by the arrow
- `dp[0]` is the single letter at the cell

Transition:
- If `next = jump[l-1][i][j]` is outside, then we can’t extend; `dp[l] = dp[l-1]` and `jump[l] = outside`.
- Else:
  - `dp[l] = dp[l-1][i][j] + dp[l-1][next]`
  - `jump[l] = jump[l-1][next]`

This is classic doubling.

**Querying a prefix of length L from a start cell**:  
Decompose `L` in binary, and for each bit from high to low:
- append `dp[bit]` to the result hash
- jump the position with `jump[bit]`
If at any point we cannot provide enough characters (walk exits early), we fail.

Time: \(O(\log L)\) per start cell.

---

### Part B: Hashing the compressed query without decompressing

Compressed form has no nested parentheses. Pattern:
- letters
- segments `(F)K` where `F` is a non-empty sequence of letters (and/or other segments? here, parentheses don’t nest, but `F` can contain letters only in valid inputs as per statement; in practice the code supports any non-parenthesis characters as letters)

We parse and build a `HashMonoid` for the fully expanded string.

The only tricky part: repeating a block `combined` with:
- hash `H`
- power `P = B^{len}`
- length `len`

Repeated `K` times:
\[
S = combined^K
\]
\[
H(S) = H \cdot (1 + P + P^2 + \dots + P^{K-1})
\]
\[
P(S) = P^K,\quad len(S)=len\cdot K
\]

So we need the geometric series:
\[
G(K,P)=1+P+P^2+\dots+P^{K-1}
\]

Instead of modular inverse (which is awkward mod \(2^{61}-1\)), the code computes this in \(O(\log K)\) using a doubling-style method (like fast exponentiation), maintaining:
- `current_pow = P^(2^t)`
- `subsum = 1 + P + ... + P^(2^t - 1)` for the current chunk
- `result` accumulates chosen chunks when bits of `K` are set

This gives `geometric_series_sum(K, P)` efficiently.

Parsing is done with a stack:
- push a marker when encountering `'('`
- push single-character monoids for letters
- when encountering `')'`, pop until marker to get the inside block `combined`, then read digits for `K`, compute the repeated monoid, and push it back.

They also wrap each whole query into `("(" + query + ")1")` so the parser always ends by processing a `')'` and leaving exactly one monoid on stack.

---

### Final check

For each query:
1. compute `target = (hash, pow, len)`
2. for every grid cell `(i,j)`:
   - compute hash of `len` letters from `(i,j)` via binary lifting
   - if successful and hashes match → candidate
3. output minimal `(row,col)` among candidates, else `NO`.

Complexities:
- Preprocessing lifting tables: \(O(RC \log 10^9)\) ≈ \(900 \cdot 31\)
- Each query parse: \(O(|compressed| + \log K\) per repetition segment) ≤ manageable
- Each query check: \(O(RC \log L)\)

Collision risk exists (hashing), but with 61-bit mod and random base it’s extremely low for contest purposes.

---

## 3) C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/strings/hashing.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

class HashMeta {
  private:
    void set_random_base() {
        seed_seq seed{
            (uint32_t)chrono::duration_cast<chrono::nanoseconds>(
                chrono::high_resolution_clock::now().time_since_epoch()
            )
                .count(),
            (uint32_t)random_device()(), (uint32_t)42
        };
        mt19937 rng(seed);
        base = uniform_int_distribution<uint64_t>(0, mod - 1)(rng);
    }

    void precompute_base_pow(size_t n) {
        base_pow.resize(n);
        base_pow[0] = 1;
        for(size_t i = 1; i < n; i++) {
            base_pow[i] = mul(base_pow[i - 1], base);
        }
    }

    static constexpr uint64_t add(uint64_t a, uint64_t b) {
        a += b + 1;
        a = (a & mod) + (a >> 61);
        return a - 1;
    }

    static constexpr uint64_t sub(uint64_t a, uint64_t b) {
        return add(a, mod - b);
    }

    static constexpr uint64_t mul(uint64_t a, uint64_t b) {
        uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
        uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
        uint64_t ret =
            (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
        ret = (ret & mod) + (ret >> 61);
        ret = (ret & mod) + (ret >> 61);
        return ret - 1;
    }

  public:
    class hash_t {
        uint64_t h;

      public:
        hash_t() : h(0) {}
        hash_t(uint64_t h) : h(h) {}
        operator uint64_t() const { return h; }

        hash_t& operator+=(const hash_t& other) {
            h = add(h, other.h);
            return *this;
        }

        hash_t& operator-=(const hash_t& other) {
            h = sub(h, other.h);
            return *this;
        }

        hash_t& operator*=(const hash_t& other) {
            h = mul(h, other.h);
            return *this;
        }

        hash_t operator+(const hash_t& other) const {
            return hash_t(*this) += other;
        }
        hash_t operator-(const hash_t& other) const {
            return hash_t(*this) -= other;
        }
        hash_t operator*(const hash_t& other) const {
            return hash_t(*this) *= other;
        }

        bool operator==(const hash_t& other) const { return h == other.h; }
        bool operator!=(const hash_t& other) const { return h != other.h; }

        bool operator<(const hash_t& other) const { return h < other.h; }
    };

    uint64_t base;
    vector<hash_t> base_pow;
    static constexpr uint64_t mod = (1ull << 61) - 1;

    void init(size_t n) {
        set_random_base();
        precompute_base_pow(n);
    }

    template<typename T>
    vector<hash_t> rabin_karp(const T& container) {
        vector<hash_t> h(container.size());
        for(size_t i = 0; i < container.size(); i++) {
            h[i] = (i ? h[i - 1] : hash_t(0)) * hash_t(base) +
                   hash_t(container[i]);
        }
        return h;
    }

    hash_t hash_range(int l, int r, const vector<hash_t>& h) {
        if(l == 0) {
            return h[r];
        }
        return h[r] - h[l - 1] * base_pow[r - l + 1];
    }
};

HashMeta hash_meta;
using hash_t = HashMeta::hash_t;

struct HashMonoid {
    hash_t h;
    hash_t pow;
    int64_t len;

    static HashMonoid identity() { return {hash_t(0), hash_t(1), 0}; }

    static HashMonoid single(char c, hash_t base) {
        return {hash_t((unsigned char)c), base, 1};
    }

    HashMonoid merge(const HashMonoid& other) const {
        return {h * other.pow + other.h, pow * other.pow, len + other.len};
    }
};

int r, c, q;
vector<string> arrows, letters;
vector<string> compressed_queries;
vector<vector<vector<pair<int, int>>>> jumps;
vector<HashMonoid> query_hashes;

void read() {
    cin >> r >> c;
    arrows.resize(r);
    letters.resize(r);
    for(int i = 0; i < r; i++) {
        cin >> arrows[i];
    }
    for(int i = 0; i < r; i++) {
        cin >> letters[i];
    }
    cin >> q;
    compressed_queries.resize(q);
    for(int i = 0; i < q; i++) {
        cin >> compressed_queries[i];
    }
}

pair<int, int> get_next_cell(int x, int y) {
    char arrow = arrows[x][y];
    int nx = x, ny = y;
    if(arrow == '<') {
        ny--;
    } else if(arrow == '>') {
        ny++;
    } else if(arrow == '^') {
        nx--;
    } else if(arrow == 'v') {
        nx++;
    }
    if(nx < 0 || nx >= r || ny < 0 || ny >= c) {
        return {-1, -1};
    }
    return {nx, ny};
}

pair<int, int> apply_jump(pair<int, int> pos, int level) {
    if(pos.first == -1) {
        return {-1, -1};
    }
    return jumps[level][pos.first][pos.second];
}

pair<HashMonoid, bool> compute_hash_from_pos(
    pair<int, int> pos, int64_t steps,
    const vector<vector<vector<HashMonoid>>>& dp
) {
    if(steps == 0) {
        return {HashMonoid::identity(), true};
    }
    if(pos.first == -1) {
        return {HashMonoid::identity(), false};
    }

    HashMonoid result = HashMonoid::identity();
    for(int i = 30; i >= 0; i--) {
        if(steps & (1LL << i)) {
            if(pos.first == -1) {
                return {HashMonoid::identity(), false};
            }

            const auto& m = dp[i][pos.first][pos.second];
            if(m.len < (1LL << i)) {
                return {HashMonoid::identity(), false};
            }

            result = result.merge(m);
            pos = apply_jump(pos, i);
        }
    }
    return {result, true};
}

hash_t geometric_series_sum(int64_t k, hash_t p) {
    if(k == 0) {
        return hash_t(0);
    }
    hash_t result = hash_t(0);
    hash_t subsum = hash_t(1);
    hash_t current_pow = p;
    while(k > 0) {
        if(k % 2 == 1) {
            result = result * current_pow + subsum;
        }
        subsum = subsum * (current_pow + hash_t(1));
        current_pow = current_pow * current_pow;
        k /= 2;
    }
    return result;
}

hash_t power(hash_t base, int64_t exp) {
    hash_t result = hash_t(1);
    while(exp > 0) {
        if(exp % 2 == 1) {
            result = result * base;
        }
        base = base * base;
        exp /= 2;
    }
    return result;
}

void solve() {
    // We should immediately think of hashes in this problem, as the pattern can
    // go up to 10^9 in length. This splits the problem in two - how to compute
    // the hash of the pattern, and how to compute the hash starting from some
    // cell (x, y).
    //
    // Note that after we know the length of the pattern, getting
    // the hash starting from cell (x, y) can be done with binary lifting, and
    // this is satisfactory because we only have R*C <= 900 cells. The binary
    // lifting is then also ~log(10^9) operations, and this is fast enough for Q
    // <= 50 queries. In terms of details for the binary lifting, we need to
    // hold the base power, the cell in 2^L jumps, and the actual hash. We have
    // to be careful about the case of going out of the table.
    //
    // In terms of computing the hash of the pattern, we need to de-compress the
    // pattern first. It's a fairly standard procedure which we can implement
    // with a stack holding the hash, base power, and length, similarly to what
    // we did in the binary power. The only part to be careful about is how to
    // handle the #repetitions, but this is essentially a sum of a geometric
    // series which we can either do with modular inverse, or in logarithmic
    // time with a procedure similar to binary exponentiation.

    hash_meta.init(1);
    hash_t base_hash = hash_t(hash_meta.base);

    int max_log = 31;
    jumps.resize(max_log);
    vector<vector<vector<HashMonoid>>> dp(
        max_log, vector<vector<HashMonoid>>(r, vector<HashMonoid>(c))
    );

    for(int l = 0; l < max_log; l++) {
        jumps[l].resize(r);
        for(int i = 0; i < r; i++) {
            jumps[l][i].resize(c, {-1, -1});
        }
    }

    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            jumps[0][i][j] = get_next_cell(i, j);
            dp[0][i][j] = HashMonoid::single(letters[i][j], base_hash);
        }
    }

    for(int l = 1; l < max_log; l++) {
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                auto next = jumps[l - 1][i][j];

                if(next.first == -1) {
                    jumps[l][i][j] = {-1, -1};
                    dp[l][i][j] = dp[l - 1][i][j];
                } else {
                    dp[l][i][j] =
                        dp[l - 1][i][j].merge(dp[l - 1][next.first][next.second]
                        );
                    jumps[l][i][j] = jumps[l - 1][next.first][next.second];
                }
            }
        }
    }

    query_hashes.resize(q);
    for(int qi = 0; qi < q; qi++) {
        string query = "(" + compressed_queries[qi] + ")1";
        vector<HashMonoid> st;

        for(int idx = 0; idx < (int)query.size(); idx++) {
            char ch = query[idx];

            if(ch == '(') {
                st.push_back({hash_t(0), hash_t(1), -1});
            } else if(ch == ')') {
                HashMonoid combined = HashMonoid::identity();
                while(st.back().len != -1) {
                    combined = st.back().merge(combined);
                    st.pop_back();
                }
                st.pop_back();

                idx++;
                int64_t cnt = 0;
                while(idx < (int)query.size() && isdigit(query[idx])) {
                    cnt = cnt * 10ll + query[idx] - '0';
                    idx++;
                }
                idx--;

                hash_t pow_repeat = power(combined.pow, cnt);
                hash_t h_repeat =
                    combined.h * geometric_series_sum(cnt, combined.pow);

                st.push_back({h_repeat, pow_repeat, combined.len * cnt});
            } else {
                st.push_back(HashMonoid::single(ch, base_hash));
            }
        }

        query_hashes[qi] = st.back();
    }

    for(int qi = 0; qi < q; qi++) {
        HashMonoid target = query_hashes[qi];

        pair<int, int> answer = {-1, -1};

        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                auto [result, success] =
                    compute_hash_from_pos({i, j}, target.len, dp);
                if(success && result.h == target.h) {
                    if(answer.first == -1 || (i < answer.first) ||
                       (i == answer.first && j < answer.second)) {
                        answer = {i, j};
                    }
                }
            }
        }

        if(answer.first == -1) {
            cout << "NO\n";
        } else {
            cout << "YES (" << answer.first + 1 << "," << answer.second + 1
                 << ")\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 4) Python solution (same approach) with detailed comments

```python
import sys
import random
import time

# We implement modulo M = 2^61 - 1 (Mersenne prime),
# similar to the C++ solution, for fast-ish hashing.
M = (1 << 61) - 1

def mod_add(a: int, b: int) -> int:
    x = a + b
    x = (x & M) + (x >> 61)
    if x >= M:
        x -= M
    return x

def mod_sub(a: int, b: int) -> int:
    return mod_add(a, M - b)

def mod_mul(a: int, b: int) -> int:
    # Python has big integers, so we can multiply then reduce.
    # Reduce using Mersenne property:
    x = a * b
    x = (x & M) + (x >> 61)
    x = (x & M) + (x >> 61)
    if x >= M:
        x -= M
    return x

def mod_pow(a: int, e: int) -> int:
    res = 1
    while e > 0:
        if e & 1:
            res = mod_mul(res, a)
        a = mod_mul(a, a)
        e >>= 1
    return res

class HashMonoid:
    __slots__ = ("h", "p", "l")  # hash, power, length

    def __init__(self, h: int, p: int, l: int):
        self.h = h
        self.p = p
        self.l = l

    @staticmethod
    def identity():
        # Empty string: H=0, B^0=1, len=0
        return HashMonoid(0, 1, 0)

    @staticmethod
    def single(ch: str, base: int):
        # Single character: H=ord(ch), power=B, len=1
        return HashMonoid(ord(ch), base, 1)

    def merge(self, other: "HashMonoid") -> "HashMonoid":
        # Concatenation:
        # H = H1 * B^{len2} + H2
        # P = B^{len1+len2} = P1 * P2
        return HashMonoid(
            mod_add(mod_mul(self.h, other.p), other.h),
            mod_mul(self.p, other.p),
            self.l + other.l
        )

def geometric_series_sum(k: int, p: int) -> int:
    """
    Return 1 + p + p^2 + ... + p^(k-1) mod M, in O(log k),
    using the same doubling technique as the C++ solution.
    """
    if k == 0:
        return 0
    result = 0     # sum for selected blocks
    subsum = 1     # sum for current block length t: 1 + p + ... + p^(t-1)
    current_pow = p  # p^t

    while k > 0:
        if k & 1:
            # result = result * p^t + subsum
            result = mod_add(mod_mul(result, current_pow), subsum)
        # double the block:
        # subsum(2t) = subsum(t) * (1 + p^t)
        subsum = mod_mul(subsum, mod_add(current_pow, 1))
        current_pow = mod_mul(current_pow, current_pow)
        k >>= 1
    return result

def parse_compressed(query: str, base: int) -> HashMonoid:
    """
    Parse compressed query (no nested parentheses) and return HashMonoid
    of the fully expanded string, without expanding explicitly.
    """
    # Wrap in "(...)1" so we always reduce at the end.
    s = "(" + query + ")1"

    # Stack of HashMonoid; marker is l = -1
    st = []

    i = 0
    while i < len(s):
        ch = s[i]
        if ch == '(':
            st.append(HashMonoid(0, 1, -1))
            i += 1
        elif ch == ')':
            # Pop until marker, building the inside group.
            combined = HashMonoid.identity()
            while st and st[-1].l != -1:
                combined = st[-1].merge(combined)
                st.pop()
            st.pop()  # pop marker

            # Read repetition count
            i += 1
            cnt = 0
            while i < len(s) and s[i].isdigit():
                cnt = cnt * 10 + (ord(s[i]) - 48)
                i += 1

            # Repeat combined cnt times:
            pow_repeat = mod_pow(combined.p, cnt)
            h_repeat = mod_mul(combined.h, geometric_series_sum(cnt, combined.p))
            st.append(HashMonoid(h_repeat, pow_repeat, combined.l * cnt))
        else:
            # Regular character
            st.append(HashMonoid.single(ch, base))
            i += 1

    return st[-1]

def get_next_cell(arrows, r, c, x, y):
    a = arrows[x][y]
    nx, ny = x, y
    if a == '<':
        ny -= 1
    elif a == '>':
        ny += 1
    elif a == '^':
        nx -= 1
    else:  # 'v'
        nx += 1
    if nx < 0 or nx >= r or ny < 0 or ny >= c:
        return (-1, -1)
    return (nx, ny)

def compute_hash_from_pos(pos, steps, dp, jumps):
    """
    Using binary lifting, compute the HashMonoid of exactly `steps` letters
    read starting at pos, or fail if we exit the grid too early.
    """
    if steps == 0:
        return (HashMonoid.identity(), True)
    x, y = pos
    if x == -1:
        return (HashMonoid.identity(), False)

    res = HashMonoid.identity()
    # We need up to 2^30 for 1e9
    for bit in range(30, -1, -1):
        if steps & (1 << bit):
            if x == -1:
                return (HashMonoid.identity(), False)
            m = dp[bit][x][y]
            # If we couldn't build a full 2^bit segment (exited early), fail.
            if m.l < (1 << bit):
                return (HashMonoid.identity(), False)
            res = res.merge(m)
            x, y = jumps[bit][x][y]
    return (res, True)

def solve():
    input_data = sys.stdin.read().strip().splitlines()
    it = iter(input_data)
    r, c = map(int, next(it).split())
    arrows = [next(it).strip() for _ in range(r)]
    letters = [next(it).strip() for _ in range(r)]
    q = int(next(it))
    queries = [next(it).strip() for _ in range(q)]

    # Random base (non-zero preferred); keep it in [1, M-1]
    random.seed(time.time_ns())
    base = random.randrange(1, M)

    max_log = 31

    # jumps[bit][i][j] = (ni,nj) after 2^bit moves
    jumps = [[ [(-1, -1) for _ in range(c)] for _ in range(r) ] for _ in range(max_log)]
    # dp[bit][i][j] = HashMonoid of 2^bit letters from (i,j), or shorter if exits
    dp = [[ [None for _ in range(c)] for _ in range(r) ] for _ in range(max_log)]

    # Level 0
    for i in range(r):
        for j in range(c):
            jumps[0][i][j] = get_next_cell(arrows, r, c, i, j)
            dp[0][i][j] = HashMonoid.single(letters[i][j], base)

    # Build lifting tables
    for bit in range(1, max_log):
        for i in range(r):
            for j in range(c):
                ni, nj = jumps[bit - 1][i][j]
                if ni == -1:
                    # Can't extend beyond exiting the grid
                    jumps[bit][i][j] = (-1, -1)
                    dp[bit][i][j] = dp[bit - 1][i][j]
                else:
                    dp[bit][i][j] = dp[bit - 1][i][j].merge(dp[bit - 1][ni][nj])
                    jumps[bit][i][j] = jumps[bit - 1][ni][nj]

    # Parse all queries
    targets = [parse_compressed(s, base) for s in queries]

    out_lines = []
    for target in targets:
        best = None
        for i in range(r):
            for j in range(c):
                got, ok = compute_hash_from_pos((i, j), target.l, dp, jumps)
                if ok and got.h == target.h:
                    if best is None or (i, j) < best:
                        best = (i, j)
        if best is None:
            out_lines.append("NO")
        else:
            out_lines.append(f"YES ({best[0]+1},{best[1]+1})")

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    solve()
```

---

## 5) Compressed editorial

- The grid defines a unique deterministic path from any start cell (functional graph).  
- Queries decompress up to \(10^9\), so compare using rolling hashes.

**Hash monoid**: store `(H, P, len)` where `P = B^len`.  
Concatenation: `H = H1*P2 + H2`, `P = P1*P2`, `len = len1+len2`.

**Binary lifting on grid** (31 levels):
- `jump[l][cell]` = cell after `2^l` moves
- `dp[l][cell]` = hash of next `2^l` letters starting at cell  
Build via doubling; if path exits early, keep shorter length.

To hash `L` letters from a start cell, walk bits of `L` and merge `dp[bit]`; fail if any required chunk is shorter.

**Parse compressed query** using a stack with a marker for `'('`.  
For a block `S` repeated `K` times:
- `P = P(S)^K`
- `H = H(S) * (1 + P(S) + ... + P(S)^(K-1))`
Compute the geometric sum in `O(log K)` (doubling method, no inverses).

For each query, compute target `(H,len)`; test all `R*C` cells via lifting; output minimal `(row,col)` match else `NO`.
