<|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) Abridged problem statement (concise)

You are given two uppercase strings:

- `A` of length `N`
- `B` of length `M` with `M < N`

A **cyclic shift** rotates a string (e.g. left shift `"ABRA"` → `"BRAA"`).

To open the lock:

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

Output:

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

If multiple shifts of `A` work, pick one requiring the **minimum number of shifts**; if still tied, prefer shifting **left**.

A solution is guaranteed to exist.

---

## 2) Key observations

1. **Cyclic shifts become substrings of a doubled string**  
   Any cyclic shift of a string `S` (length `L`) equals a substring of `S+S` of length `L`.  
   So:
   - shifts of `A` ↔ substrings of `A2 = A + A` of length `N` starting at `0..N-1`
   - shifts of `B` ↔ substrings of `B2 = B + B` of length `M` starting at `0..M-1`

2. **Lexicographically smallest cyclic shift can be found by comparing candidates**  
   To compare two candidate shifts of `B`, we need the first position where they differ:
   - compute `LCP` (longest common prefix) length between the two substrings
   - then compare the next character

3. **Fast LCP via rolling hash + binary search**  
   With polynomial rolling hash and prefix hashes, substring equality is O(1).  
   Then LCP can be computed in `O(log M)` via binary search on length.

4. **Checking “≤ 1 mismatch” using at most two LCPs**  
   Let `X = A2[pos : pos+M]` and `Y = B'`.  
   - `l1 = LCP(X, Y)`
   - if `l1 == M` ⇒ 0 mismatches  
   - else skip the mismatching character and compute LCP on the remainder:
     `l2 = LCP(X[l1+1:], Y[l1+1:])`  
     If `l1 + 1 + l2 == M` ⇒ exactly 1 mismatch, else ≥ 2

5. **Tie-breaking for shifting `A`**  
   Minimum number of shifts means minimal distance `d` where:
   - left shift by `d` ↔ start index `d`
   - right shift by `d` ↔ start index `N - d`
   Check in order:
   `d = 0,1,2,...` and for each `d` test left first, then right.

---

## 3) Full solution approach

### Step A: Preprocess for cyclic shifts
- Read `N, M, A, B`
- Build doubled strings:
  - `A2 = A + A`
  - `B2 = B + B`

### Step B: Rolling hash preparation
- Precompute powers of base.
- Build prefix hash arrays for `A2` and `B2`.
- Implement:
  - `hash(l, r)` for a substring in O(1)
  - `lcp(i, j, maxLen, whichStrings)` using binary search + hashes

### Step C: Find lexicographically smallest cyclic shift of `B`
- For each start `i` in `0..M-1`, compare `B2[i:i+M]` with current best using LCP.
- Keep `best_b` = start index of minimal shift.
- Output `B' = B2[best_b : best_b+M]`.

### Step D: Find the best shift of `A` matching `B'` with ≤ 1 mismatch
- Define predicate `ok(pos)` that checks whether `A2[pos:pos+M]` differs from `B'` in at most one position using two LCP calls.
- Search smallest shift count:
  - for `d = 0..floor(N/2)`:
    - if `ok(d)` choose it (left shift by `d`)
    - else if `d>0` and `ok(N-d)` choose it (right shift by `d`)
- This guarantees minimal number of shifts; left is preferred on ties.

### Step E: Output
- Line 1: `B2[best_b : best_b+M]`
- Line 2: `A2[best_a : best_a+N]`

Complexity:
- Building hashes: `O(N + M)`
- Minimal shift of `B`: `O(M log M)`
- Finding shift of `A`: up to `O(N log M)`
Fits easily under the limits with efficient hashing.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  Rolling hash mod (2^61 - 1), a common fast prime-like modulus.
  This implementation uses the standard trick for fast multiplication and reduction.
*/
struct RH61 {
    static constexpr uint64_t MOD = (1ULL << 61) - 1;

    uint64_t base;
    vector<uint64_t> pows;   // base^i mod MOD

    // Add modulo MOD
    static inline uint64_t add(uint64_t a, uint64_t b) {
        a += b + 1;
        a = (a & MOD) + (a >> 61);
        return a - 1;
    }

    // Sub modulo MOD
    static inline uint64_t sub(uint64_t a, uint64_t b) {
        return add(a, MOD - b);
    }

    // Mul modulo MOD using 64-bit split trick
    static inline uint64_t mul(uint64_t a, uint64_t b) {
        uint64_t l1 = (uint32_t)a, h1 = a >> 32;
        uint64_t l2 = (uint32_t)b, h2 = b >> 32;
        uint64_t l = l1 * l2;
        uint64_t m = l1 * h2 + l2 * h1;
        uint64_t h = h1 * h2;

        // Carefully derived reduction for 2^61-1
        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;
    }

    void init(size_t maxLen) {
        // Random base reduces collision risk
        uint64_t seed = (uint64_t)chrono::high_resolution_clock::now()
                            .time_since_epoch().count();
        mt19937_64 rng(seed);
        uniform_int_distribution<uint64_t> dist(1, MOD - 2);
        base = dist(rng);

        pows.assign(maxLen + 1, 0);
        pows[0] = 1;
        for (size_t i = 1; i <= maxLen; i++) {
            pows[i] = mul(pows[i - 1], base);
        }
    }

    // Build prefix hashes: pref[i+1] = hash(s[0..i])
    vector<uint64_t> prefix(const string &s) const {
        vector<uint64_t> pref(s.size() + 1, 0);
        for (size_t i = 0; i < s.size(); i++) {
            pref[i + 1] = add(mul(pref[i], base), (uint64_t)(unsigned char)s[i]);
        }
        return pref;
    }

    // Hash of substring s[l..r) using prefix array
    uint64_t rangeHash(const vector<uint64_t> &pref, int l, int r) const {
        // pref[r] - pref[l] * base^(r-l)
        return sub(pref[r], mul(pref[l], pows[r - l]));
    }
};

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

    int N, M;
    cin >> N >> M;
    string A, B;
    cin >> A >> B;

    // Double strings to represent cyclic shifts as substrings
    string A2 = A + A;
    string B2 = B + B;

    RH61 rh;
    // We will query up to length N (and M), and indices are within doubled strings.
    rh.init(2 * (size_t)N + 5);

    auto hA = rh.prefix(A2);
    auto hB = rh.prefix(B2);

    // LCP between A2[i:] and B2[j:] up to maxLen
    auto lcpAB = [&](int i, int j, int maxLen) -> int {
        int lo = 0, hi = maxLen;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (rh.rangeHash(hA, i, i + mid) == rh.rangeHash(hB, j, j + mid))
                lo = mid;
            else
                hi = mid - 1;
        }
        return lo;
    };

    // LCP between B2[i:] and B2[j:] up to maxLen (for comparing shifts of B)
    auto lcpBB = [&](int i, int j, int maxLen) -> int {
        int lo = 0, hi = maxLen;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (rh.rangeHash(hB, i, i + mid) == rh.rangeHash(hB, j, j + mid))
                lo = mid;
            else
                hi = mid - 1;
        }
        return lo;
    };

    // Compare two cyclic shifts of B (start i and j), each length M
    auto shiftLess = [&](int i, int j) -> bool {
        int l = lcpBB(i, j, M);
        if (l == M) return false;          // equal shifts
        return B2[i + l] < B2[j + l];      // first differing char decides
    };

    // Step 1: find lexicographically smallest cyclic shift of B
    int best_b = 0;
    for (int i = 1; i < M; i++) {
        if (shiftLess(i, best_b)) best_b = i;
    }

    // Step 2: check if A2[pos:pos+M] matches B2[best_b:best_b+M] with <= 1 mismatch
    auto ok = [&](int pos) -> bool {
        int l1 = lcpAB(pos, best_b, M);
        if (l1 == M) return true;          // 0 mismatches

        // mismatch at l1, try to skip it and match the rest
        if (l1 == M - 1) return true;      // only last char mismatches -> 1 mismatch

        int rest = M - l1 - 1;
        int l2 = lcpAB(pos + l1 + 1, best_b + l1 + 1, rest);
        return (l1 + 1 + l2 == M);         // remainder matches => exactly 1 mismatch
    };

    // Choose best shift of A by minimal number of shifts, tie -> left
    int best_a = -1;
    for (int d = 0; d <= N / 2 && best_a == -1; d++) {
        // left shift by d => start at d
        if (ok(d)) {
            best_a = d;
            break;
        }
        // right shift by d => start at N - d
        // avoid duplicate when d==0 or N-d==d
        if (d > 0 && N - d != d && ok(N - d)) {
            best_a = N - d;
            break;
        }
    }

    // Construct final strings
    string Bprime = B2.substr(best_b, M);
    string Ashift = A2.substr(best_a, N);

    cout << Bprime << "\n" << Ashift << "\n";
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
import random
import time

# Rolling hash modulo 2^61 - 1
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 using the identity for MOD = 2^61-1:
    # x mod MOD = (x & MOD) + (x >> 61), repeated.
    x = a * b
    x = (x & MOD) + (x >> 61)
    x = (x & MOD) + (x >> 61)
    if x >= MOD:
        x -= MOD
    return x

class RollingHash61:
    def __init__(self, max_len):
        seed = time.time_ns() ^ random.getrandbits(64)
        rng = random.Random(seed)
        self.base = rng.randrange(1, MOD - 1)

        self.pows = [1] * (max_len + 1)
        for i in range(1, max_len + 1):
            self.pows[i] = mod_mul(self.pows[i - 1], self.base)

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

    def range_hash(self, pref, l, r):
        # hash(s[l:r]) = pref[r] - pref[l] * base^(r-l)
        return mod_sub(pref[r], mod_mul(pref[l], self.pows[r - l]))

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    N, M = map(int, data[:2])
    A = data[2].strip()
    B = data[3].strip()

    # Double strings to turn cyclic shifts into substrings
    A2 = A + A
    B2 = B + B

    rh = RollingHash61(2 * N + 5)
    hA = rh.prefix(A2)
    hB = rh.prefix(B2)

    def lcp(pref1, pref2, i, j, max_len):
        """Longest common prefix length between s1[i:] and s2[j:], capped by max_len."""
        lo, hi = 0, max_len
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if rh.range_hash(pref1, i, i + mid) == rh.range_hash(pref2, j, j + mid):
                lo = mid
            else:
                hi = mid - 1
        return lo

    # Compare cyclic shifts of B starting at i and j (length M)
    def shift_less(i, j):
        common = lcp(hB, hB, i, j, M)
        if common == M:
            return False
        return B2[i + common] < B2[j + common]

    # Step 1: minimal cyclic shift of B
    best_b = 0
    for i in range(1, M):
        if shift_less(i, best_b):
            best_b = i

    # Check if A2[pos:pos+M] differs from B' by at most one character
    def ok(pos):
        l1 = lcp(hA, hB, pos, best_b, M)
        if l1 == M:
            return True  # exact match
        if l1 == M - 1:
            return True  # only last char differs

        # Skip the mismatching character at l1 and verify the remainder matches
        rest = M - l1 - 1
        l2 = lcp(hA, hB, pos + l1 + 1, best_b + l1 + 1, rest)
        return (l1 + 1 + l2 == M)

    # Step 2: choose shift of A with minimal number of shifts; tie -> left
    best_a = None
    for d in range(0, N // 2 + 1):
        # left shift by d => start index d
        if ok(d):
            best_a = d
            break
        # right shift by d => start index N-d
        if d > 0 and (N - d) != d and ok(N - d):
            best_a = N - d
            break

    Bprime = B2[best_b:best_b + M]
    Ashift = A2[best_a:best_a + N]
    sys.stdout.write(Bprime + "\n" + Ashift + "\n")

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

If you want an even faster (and collision-free) approach for Step 1, you can replace the “minimal cyclic shift via hashing” with **Booth’s algorithm** (O(M)), while keeping hashing for the “≤ 1 mismatch” matching step.