<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

392. Cyclic Troubles
Time limit per test: 1 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



A package has been delivered to the King of Berland containing a game called "Bercycles". It's an entertaining single-player game with simple rules:

You're given a rectangular field consisting of R rows and C columns, which result in R*C cells total. Each cell contains a lowercase Latin letter and an arrow pointing one of the four following directions: left, right, up, or down.
You choose the cell at which you wish to start the game and make a number of moves. At each move you have to write down the letter from the current cell and move one cell in the direction shown by the arrow at this cell. You can stop moving any time you want. If you leave the field, the process stops automatically and you're not allowed to move anymore.
The letters you write down during your movements form a word that you read during the game.


After reading the rules the King of Berland realized that he is in trouble. He is given a number of words and for each word he is to determine whether it is possible to play the game and read this word. Please help the King to solve this challenging problem.

Input
The first line of input file contains integer numbers R and C (1 ≤ R ≤ 30, 1 ≤ C ≤ 30) — number of rows and columns correspondingly. The following R lines describe arrows on the field. Each of these R lines contains exactly C characters. Each character denotes a direction:

'' character - LEFT
'' character - RIGHT
'' character - UP
'' character - DOWN


Then R more lines follow, describing letters on the field. Each of these R lines contains exactly C characters. Each character is a lowercase Latin letter 'a'-'z'.

Then one more line follows containing a single integer number Q (1 ≤ Q ≤ 50) — number of queries. Each of the following Q lines contains a word for which you should solve the problem.

To reduce the size of input files, these Q words are given to you in a compressed form. A compressed form of a word may contain non-empty letter sequence F enclosed in parentheses, followed by a positive integer number K. It means that the fragment F should be repeated K times.

For example, the string "a(xy)2y(ab)3abz" is one of the compressed forms of the string "axyxyyababababz". Note: parentheses may not be enclosed into each other, so "a(xy)2y((ab)2)2z" is not a compressed form of the same word. Leading zeroes are not allowed as well in a compressed form, so no queries like "(ab)02" will be given to you.

Input file will not contain any malformed compressed words. The length of each compressed query will be between 1 and 2000 characters. When decompressed, the length of each query will be no longer than 109 characters.

Output
For each query you should print a single line to the output file. If the corresponding compressed word can be read on the field, then the line should contain "YES (X,Y)", where X and Y correspond to the row and column in the field where you should start in order to read the given word. Rows and columns are numbered starting from 1.

If the word can't be found in the field, you should print a single word "NO" in the line. If there is more than one solution, print the one with a minimal row X. If there is more than one solution with the same minimal row, print one that minimizes column Y. Please see sample output for further clarifications on the output file format.

Example(s)
sample input
sample output
2 4
>>>v
<^<<
abcd
efgh
6
abcdhgf
bcdhgf
(bcdhgf)100
a(bcdhgf)100bc
b(cdhgfbc)1d
hello
YES (1,1)
YES (1,2)
YES (1,2)
YES (1,1)
YES (1,2)
NO

<|response|>
## 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 the next cell (or outside 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

You may stop at any time; if you step outside the grid, the process stops automatically.

For each of \(Q \le 50\) queries, a word is given in **compressed** form where `(F)K` means repeat string `F` exactly `K` times. Parentheses do **not** nest. Compressed length \(\le 2000\), 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) Key observations needed to solve the problem

1. **Deterministic walk**: From each cell there is exactly one outgoing arrow, so starting cell uniquely determines the entire sequence of visited cells (until leaving the grid or looping).

2. **Very long queries**: Decompressed query length can be up to \(10^9\), so we cannot expand the word.

3. **Small grid**: \(R \cdot C \le 900\). We can test every start cell per query if each test is ~\(O(\log L)\).

4. **Use hashing + binary lifting**:
   - Build a structure that can compute the hash of the first \(L\) letters along the arrow-walk starting from any cell in \(O(\log L)\) (binary lifting / doubling).
   - Parse the compressed query into a hash (and length) without decompression, using polynomial rolling hash and fast handling of repetitions.

---

## 3) Full solution approach

We combine two techniques:

### A. Represent strings with a “hash monoid” (hash + power + length)

Use polynomial rolling hash:

\[
H(s_0s_1\dots s_{n-1}) = (((s_0)\cdot B + s_1)\cdot B + \dots )\cdot B + s_{n-1}
\]

Store a triple:

- `h` = hash of the string
- `pow` = \(B^{len}\)
- `len` = length

Concatenation \(A+B\):

- \(H(A+B) = H(A)\cdot B^{|B|} + H(B)\)
- \(B^{|A+B|} = B^{|A|}\cdot B^{|B|}\)
- \(|A+B| = |A| + |B|\)

So we can build big hashes from smaller parts.

We use modulus \(M = 2^{61}-1\) (fast, low collision risk) and a random base \(B\).

---

### B. Binary lifting on the grid to hash a path prefix quickly

Precompute for each cell and each level \(k\) (where \(2^k \le 10^9\), so \(k \le 30\)):

- `jump[k][cell]`: the cell reached after \(2^k\) moves (or outside)
- `dp[k][cell]`: hash-monoid of the **sequence of letters read** from `cell` for the next \(2^k\) visited cells

Base \(k=0\):

- `jump[0][cell]` = neighbor indicated by arrow (or outside)
- `dp[0][cell]` = monoid of the single letter in this cell

Transition:

Let `mid = jump[k-1][cell]` (cell after \(2^{k-1}\) moves)

- If `mid` is outside, we can’t extend:
  - `jump[k][cell] = outside`
  - `dp[k][cell] = dp[k-1][cell]` (it may be shorter than \(2^k\) logically)
- Otherwise:
  - `dp[k][cell] = dp[k-1][cell] + dp[k-1][mid]`
  - `jump[k][cell] = jump[k-1][mid]`

**Querying** the hash of first \(L\) letters from a start cell:

Decompose \(L\) in bits, and for each bit \(k\) set:

- append `dp[k]` to result
- move start cell to `jump[k]`

If at any step a required `dp[k]` chunk is incomplete (path leaves grid before providing \(2^k\) letters), fail.

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

---

### C. Parse the compressed query and hash it without decompression

We parse the query using a stack:

- Push a marker when seeing `'('`
- Push single-letter monoids for normal letters
- When seeing `')'`, pop until marker to get the inside block monoid `block`
- Read integer \(K\) after `')'`
- Replace `block` by `block` repeated \(K\) times

#### Handling repetition efficiently

Let `block` have:

- hash \(H\)
- power \(P = B^{len}\)
- length \(len\)

Then:

- total length = \(len \cdot K\)
- total power = \(P^K\)
- total hash:

\[
H \cdot (1 + P + P^2 + \dots + P^{K-1})
\]

So we need the geometric sum \(G(K,P)\) modulo \(M\).  
Because modulus is \(2^{61}-1\) (no easy modular inverse in the implementation), compute \(G(K,P)\) in \(O(\log K)\) with a doubling method (similar to binary exponentiation).

Finally, for each query:

1. compute its `(hash, len)`
2. try all 900 start cells using binary lifting to get prefix hash of length `len`
3. if hash matches: keep minimal (row, col)

---

## 4) C++ implementation

```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;
}
```

---

## 5) Python implementation with detailed comments

```python
import sys
import random
import time

# Modulus M = 2^61 - 1 (Mersenne prime)
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_mul(a: int, b: int) -> int:
    # Python big ints make multiplication easy; then reduce using Mersenne trick.
    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:
    r = 1
    while e > 0:
        if e & 1:
            r = mod_mul(r, a)
        a = mod_mul(a, a)
        e >>= 1
    return r

class HashMonoid:
    """
    Represents a string S by:
      h = hash(S)
      p = B^len(S)
      l = len(S)
    """
    __slots__ = ("h", "p", "l")

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

    @staticmethod
    def identity():
        return HashMonoid(0, 1, 0)

    @staticmethod
    def single(ch: str, base: int):
        return HashMonoid(ord(ch), base, 1)

    def merge(self, other: "HashMonoid") -> "HashMonoid":
        # Concatenation: H = H1 * B^{len2} + H2
        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 doubling (no modular inverse needed).
    """
    if k == 0:
        return 0

    res = 0
    subsum = 1       # for current block size t: 1 + p + ... + p^(t-1)
    current_pow = p  # p^t

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

def parse_compressed(query: str, base: int) -> HashMonoid:
    """
    Parse compressed form (no nested parentheses) into HashMonoid
    without decompressing.
    """
    s = "(" + query + ")1"  # force final reduction

    st = []
    i = 0
    while i < len(s):
        ch = s[i]
        if ch == '(':
            # marker: l = -1
            st.append(HashMonoid(0, 1, -1))
            i += 1
        elif ch == ')':
            # pop until marker, build combined
            combined = HashMonoid.identity()
            while st[-1].l != -1:
                combined = st[-1].merge(combined)
                st.pop()
            st.pop()  # remove 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

            pow_rep = mod_pow(combined.p, cnt)
            h_rep = mod_mul(combined.h, geometric_series_sum(cnt, combined.p))
            st.append(HashMonoid(h_rep, pow_rep, combined.l * cnt))
        else:
            st.append(HashMonoid.single(ch, base))
            i += 1

    return st[-1]

def solve():
    data = sys.stdin.read().strip().splitlines()
    it = iter(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 in [1, M-1]
    random.seed(time.time_ns())
    base = random.randrange(1, M)

    def next_cell(x: int, y: int):
        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)

    MAXLOG = 31  # enough for up to 2^30 >= 1e9

    # jump[k][i][j] = cell after 2^k moves
    jump = [[ [(-1, -1) for _ in range(C)] for _ in range(R) ] for _ in range(MAXLOG)]
    # dp[k][i][j] = hash monoid of next 2^k letters from (i,j) (may be incomplete)
    dp = [[ [None for _ in range(C)] for _ in range(R) ] for _ in range(MAXLOG)]

    # base layer
    for i in range(R):
        for j in range(C):
            jump[0][i][j] = next_cell(i, j)
            dp[0][i][j] = HashMonoid.single(letters[i][j], base)

    # build doubling tables
    for k in range(1, MAXLOG):
        for i in range(R):
            for j in range(C):
                ni, nj = jump[k-1][i][j]
                if ni == -1:
                    jump[k][i][j] = (-1, -1)
                    dp[k][i][j] = dp[k-1][i][j]
                else:
                    dp[k][i][j] = dp[k-1][i][j].merge(dp[k-1][ni][nj])
                    jump[k][i][j] = jump[k-1][ni][nj]

    def compute_hash_from(start, L: int):
        """
        Compute hash of exactly L letters along arrow-walk from start.
        Return (HashMonoid, success).
        """
        if L == 0:
            return (HashMonoid.identity(), True)
        x, y = start
        if x == -1:
            return (HashMonoid.identity(), False)

        res = HashMonoid.identity()
        for k in range(30, -1, -1):
            if L & (1 << k):
                if x == -1:
                    return (HashMonoid.identity(), False)
                chunk = dp[k][x][y]
                if chunk.l < (1 << k):
                    return (HashMonoid.identity(), False)
                res = res.merge(chunk)
                x, y = jump[k][x][y]
        return (res, True)

    out = []
    for q in queries:
        target = parse_compressed(q, base)
        best = None

        for i in range(R):
            for j in range(C):
                got, ok = compute_hash_from((i, j), target.l)
                if ok and got.h == target.h:
                    if best is None or (i, j) < best:
                        best = (i, j)

        if best is None:
            out.append("NO")
        else:
            out.append(f"YES ({best[0] + 1},{best[1] + 1})")

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

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