<|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.

439. A Secret Book
Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Many organizers of math contests notice that their students are not really good in solving so-called two-step problems, which are the problems that can be solved by solving two weakly related sub-problems consecutively. In fact, it is easier to them to solve one-step problem which is much more complex than both sub-problems of the two-step problem. Now, you have got a book with the annotation on cover which says that this book holds an explanation of the mystery of that paradox. Unfortunately, the book is locked with a special lock, but there is a detailed instruction on how to open it.

The lock is made of two tapes with capital Latin letters printed on them. All letters on both tapes have identical width. The second tape is placed directly below the first, and they are aligned by left border. To have better understanding of this, you can think of these tapes as two strings of letters printed with monospaced font, one under another. The length of the second tape (string) is strictly less than the length of the first one. Using the lock mechanism, you can shift any tape left or right by one letter. This shift is cyclic, that is, after a shift to the left, string "ABRA" becomes "BRAA". To open the lock, you must shift the second tape so that the lexicographic order of resulting string will be the least possible. After that you must shift the first tape in such way that the beginning of the first string will match the whole second string. For example, let us assume that the first tape contains string "KADAABRA" and the second tape contains "ABRA". On the first step we should shift the second string by one letter to the right, so we get "AABR" (the lexicographically smallest shift of the string "ABRA"). After that we shift the first string by three letters to the left, resulting in string "AABRAKAD" which begins with "AABR". Additionally, the lock mechanism accepts combinations where any one letter in the second string differs from the corresponding letter in the first string. Thus, if the first string is "KADABRA" and the second is "AABR", it is acceptable to shift first string to get "DABRAKA", which begins with "DABR" that differs from "AABR" by one letter, and the lock will be opened.

Given the strings on the two tapes, find a way to open the lock. It is guaranteed that the solution exists.

Input
The first line of input contains two integers N and M which indicate the number of letters on the first and second tapes, respectively (). The second line consists of N capital Latin letters — the string printed on the first tape. The third line consists of M capital Latin letters — the string printed on the second tape.

Output
Output two lines. The first line should contain the resulting string on the second tape. The second line should contain the resulting string on the first tape. If several solutions are possible, output a solution which shifts the first tape the minimal number of times. If more than one solution still exists, output a solution where the first tape is being shifted to the left.

Example(s)
sample input
sample output
7 4
KADABRA
ABRA
AABR
DABRAKA

<|response|>
## 1) Concise abridged problem statement

You are given two strings of uppercase letters:

- First tape string `A` of length `N`
- Second tape string `B` of length `M`, with `M < N`

A **cyclic shift** moves characters left/right with wrap-around (e.g., left shift `"ABRA"` → `"BRAA"`).

To open the lock:

1. Cyclically shift `B` to obtain the **lexicographically smallest** cyclic shift of `B`. Call this resulting string `B'`.
2. Cyclically shift `A` so that its first `M` characters match `B'` **with at most one mismatching position**.

Output:
- Line 1: `B'`
- Line 2: the chosen shifted version of `A`

If multiple `A`-shifts work, choose one with **minimum number of shifts**; if still tied, choose the **left shift** direction.

A solution is guaranteed to exist.

---

## 2) Detailed editorial

### Key observations

#### A) Handling cyclic shifts by doubling the string
A cyclic shift corresponds to taking a length-`L` substring of `S+S`:
- Any cyclic shift of `S` (length `L`) equals `S2[i : i+L)` where `S2 = S + S` and `0 ≤ i < L`.

So we build:
- `A2 = A + A` (length `2N`)
- `B2 = B + B` (length `2M`)

Then:
- A cyclic shift of `B` is `B2[i : i+M)`, `i in [0, M-1]`
- A cyclic shift of `A` is `A2[i : i+N)`, `i in [0, N-1]`

#### B) Need fast substring comparisons ⇒ rolling hash + LCP by binary search
To compare two candidate cyclic shifts lexicographically, we need to find the first position where they differ (their LCP).

We use Rabin-Karp polynomial hashing over mod 2^61 - 1 (a fast Mersenne-like prime), which supports:
- `hash(S[l..r])` in O(1) after O(n) preprocessing
- LCP between two substrings by binary searching the length and comparing hashes: O(log L)

Define:
`lcp(i, j, max_len)` = longest common prefix length between substrings starting at positions `i` and `j` with maximum length `max_len`.

---

### Step 1: Find lexicographically smallest cyclic shift of `B`

We want:
```
best_b = argmin over i in [0..M-1] of B2[i:i+M)
```

To compare shifts `i` and `j`:
1. `l = lcp(i, j, M)`
2. If `l == M`, they are equal.
3. Else compare `B2[i+l]` vs `B2[j+l]`.

This is O(M log M) time (M comparisons, each LCP O(log M)).

---

### Step 2: Find a shift of `A` whose prefix matches `B'` with at most 1 mismatch

Let `B' = B2[best_b : best_b+M)`.

For each candidate starting position `pos_a` in `A2`, we need the first `M` chars of that shifted `A` to differ from `B'` in at most one position.

#### Counting mismatches using at most two LCP calls

- Compute `l1 = lcp(pos_a, best_b, M)` between `A2[pos_a:]` and `B2[best_b:]`.
  - If `l1 == M`: exact match, 0 mismatches.
  - Otherwise the first mismatch is at index `l1`.
- Skip that mismatching character and match the remainder:
  - Compute `l2 = lcp(pos_a + l1 + 1, best_b + l1 + 1, M - l1 - 1)`
  - If `l1 + 1 + l2 == M`, then everything else matches, exactly 1 mismatch.
  - Otherwise at least 2 mismatches.

So mismatch-counting is O(log M).

---

### Tie-breaking on the shift of `A`

We must:
1. Minimize number of shifts needed to reach the chosen cyclic shift from original `A`.
2. If tied, prefer left shift.

If we represent a left shift by `d` positions as taking `A2[d : d+N)`, then:
- Left shift by `d` corresponds to start index `d`
- Right shift by `d` corresponds to left shift by `N-d` (start index `N-d`)

The solution searches in increasing `d = 0..floor(N/2)` and checks:
- left shift `d`
- then (if different) right shift `d` i.e. start at `N-d`

Guaranteed solution exists, so it will find one.

---

### Complexity
- Hash preprocessing: O(N + M)
- Smallest shift of `B`: O(M log M)
- Finding shift of `A`: up to N candidates worst-case, each O(log M), so O(N log M)

Overall O(N log N), fits constraints with fast hashing.

---

## 3) C++ implementation

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

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

        // For use in std::map and std::set
        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;

int n, m;
string A, B;

void read() {
    cin >> n >> m;
    cin >> A >> B;
    A = A + A;
    B = B + B;
}

void solve() {
    // We could potentially solve this with suffix trees or arrays, but the "1
    // character difference" condition makes this a bit more annoying. Instead,
    // there is a fairly direct way with hashing. We can recall the O(n log^2 n)
    // algorithm for suffix arrays that is based on hashing: we define a lcp(i,
    // j) function that finds the longest common prefix of the suffix starting
    // at i and j using binary search and hashing in log(n). Then the full
    // suffix array algorithm is just using this lcp(i, j) in the cmp function
    // of a std::sort.
    //
    // The idea of using hashes and binary search to find the first mismatch can
    // also be generalized - it doesn't have to be for building the suffix
    // array. In particular, in this problem we first need to find the
    // lexicographically smallest cycle shift, which can be done in O(n) calls
    // of the lcp(i, j) oracle, by just thinking of it as finding the minimum in
    // an array, but with just a slightly more complicated compare function.
    // Alternatively, we could use Booth's algorithm which is heavily based on
    // Knuth-Morris-Pratt (KMP) and is a bit faster (overall O(n)), but in the
    // second part of the problem we will anyways need hashes so an O(n log n)
    // approach is fine.
    //
    // After we have found the minimal cyclic shift (we will call this the
    // pattern), we want to find a substring in the first string that matches
    // the pattern with 1 character error allowed. Let's rephrase this instead
    // as finding the first <= 2 mismatches. This can be done with two calls of
    // lcp(i, j) which we already know are in O(log). We have to be careful
    // about the indices when we implement this.
    //
    // In terms of implementation, we start with A = A + A and B = B + B. This
    // is so that we only look at substrings of length m, and don't care about
    // the actual cycle shifts.
    //
    // Overall, the time complexity is O(n log n).

    hash_meta.init(2 * n);
    vector<hash_t> ph_a = hash_meta.rabin_karp(A);
    vector<hash_t> ph_b = hash_meta.rabin_karp(B);

    auto lcp = [&](int i, int j, vector<hash_t>& ph_i, vector<hash_t>& ph_j,
                   int max_len) {
        int lo = 0, hi = max_len;
        while(lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if(hash_meta.hash_range(i, i + mid - 1, ph_i) ==
               hash_meta.hash_range(j, j + mid - 1, ph_j)) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        return lo;
    };

    auto cmp_cyclic = [&](int i, int j) {
        int l = lcp(i, j, ph_b, ph_b, m);
        if(l == m) {
            return false;
        }
        return B[i + l] < B[j + l];
    };

    int best_b = 0;
    for(int i = 1; i < m; i++) {
        if(cmp_cyclic(i, best_b)) {
            best_b = i;
        }
    }

    auto count_mismatches = [&](int pos_a) {
        int l1 = lcp(pos_a, best_b, ph_a, ph_b, m);
        if(l1 == m) {
            return 0;
        }
        if(l1 == m - 1) {
            return 1;
        }
        int l2 = lcp(pos_a + l1 + 1, best_b + l1 + 1, ph_a, ph_b, m - l1 - 1);
        if(l1 + 1 + l2 == m) {
            return 1;
        }
        return 2;
    };

    int best_a = -1;
    for(int d = 0; d <= n / 2 && best_a == -1; d++) {
        if(count_mismatches(d) <= 1) {
            best_a = d;
        } else if(d > 0 && n - d != d && count_mismatches(n - d) <= 1) {
            best_a = n - d;
        }
    }

    string result_b = B.substr(best_b, m);
    string result_a = A.substr(best_a, n);

    cout << result_b << "\n";
    cout << result_a << "\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 with detailed comments

```python
import sys
import random
import time

# We'll implement rolling hash with mod = 2^61 - 1 (same modulus idea as C++).
# Python integers are arbitrary precision, so we can implement safe reduction.

MOD = (1 << 61) - 1

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

def mod_sub(a, b):
    return mod_add(a, MOD - b)

def mod_mul(a, b):
    # Multiply then reduce mod (2^61-1) using the identity:
    # x mod (2^61-1) = (x & MOD) + (x >> 61), repeated once or twice.
    x = a * b
    x = (x & MOD) + (x >> 61)
    x = (x & MOD) + (x >> 61)
    if x >= MOD:
        x -= MOD
    return x

class RollingHash:
    def __init__(self, max_len):
        # Random base in [1..MOD-2]
        seed = int(time.time_ns()) ^ random.getrandbits(64)
        rng = random.Random(seed)
        self.base = rng.randrange(1, MOD - 1)

        # Precompute powers of base up to max_len
        self.pow = [1] * (max_len + 1)
        for i in range(1, max_len + 1):
            self.pow[i] = mod_mul(self.pow[i - 1], self.base)

    def prefix_hash(self, s):
        # Build prefix hashes:
        # h[i+1] = hash(s[0..i]) (length i+1)
        h = [0] * (len(s) + 1)
        for i, ch in enumerate(s):
            h[i + 1] = mod_add(mod_mul(h[i], self.base), ord(ch))
        return h

    def range_hash(self, h, l, r):
        # hash of s[l:r] (half-open)
        # = h[r] - h[l] * base^(r-l)
        return mod_sub(h[r], mod_mul(h[l], self.pow[r - l]))

def solve():
    data = sys.stdin.read().strip().split()
    n, m = map(int, data[:2])
    A = data[2].strip()
    B = data[3].strip()

    # Double strings to model cyclic shifts as substrings
    A2 = A + A
    B2 = B + B

    # Prepare hashing (need powers up to 2*n, safe for all queries we do)
    rh = RollingHash(2 * n + 5)
    ha = rh.prefix_hash(A2)
    hb = rh.prefix_hash(B2)

    def lcp_a_b(i, j, max_len):
        """LCP between A2[i:] and B2[j:] up to max_len."""
        lo, hi = 0, max_len
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if rh.range_hash(ha, i, i + mid) == rh.range_hash(hb, j, j + mid):
                lo = mid
            else:
                hi = mid - 1
        return lo

    def lcp_b_b(i, j, max_len):
        """LCP between B2[i:] and B2[j:] up to max_len."""
        lo, hi = 0, max_len
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if rh.range_hash(hb, i, i + mid) == rh.range_hash(hb, j, j + mid):
                lo = mid
            else:
                hi = mid - 1
        return lo

    # Compare two cyclic shifts of B lexicographically
    def cmp_shift(i, j):
        l = lcp_b_b(i, j, m)
        if l == m:
            return False
        return B2[i + l] < B2[j + l]

    # Step 1: lexicographically smallest cyclic shift of B
    best_b = 0
    for i in range(1, m):
        if cmp_shift(i, best_b):
            best_b = i

    # Step 2: check if A2[pos:pos+m] differs from B2[best_b:best_b+m] by <= 1 char
    def mismatches_le_1(pos):
        l1 = lcp_a_b(pos, best_b, m)
        if l1 == m:
            return True  # 0 mismatches
        if l1 == m - 1:
            return True  # exactly 1 mismatch (last char)
        # skip one mismatch at l1, then remaining must match
        l2 = lcp_a_b(pos + l1 + 1, best_b + l1 + 1, m - l1 - 1)
        return (l1 + 1 + l2 == m)

    # Choose shift of A with minimal shift count; tie -> left shift.
    best_a = None
    for d in range(0, n // 2 + 1):
        # left shift by d => start index d
        if mismatches_le_1(d):
            best_a = d
            break
        # right shift by d => start index n-d (avoid duplicates)
        if d > 0 and n - d != d and mismatches_le_1(n - d):
            best_a = n - d
            break

    # Output results
    result_b = B2[best_b:best_b + m]
    result_a = A2[best_a:best_a + n]
    sys.stdout.write(result_b + "\n" + result_a + "\n")

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