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

268. Hyper Almost Permutative String
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



The string is called permutative if it consists of N first capital letters in arbitrary order (i.e. "A", "BA", "CABED", "DCBA" for N=1, 2, 5, 4 correspondingly). The string is called almost permutative, if it is possible to obtain permutative string from it by removing exactly one symbol (i.e. "BA", "ABCCD", "BCAB", "ATB" -- almost permutative strings for N=1, 4, 3, 2 correspondingly). The string is called hyper almost permutative for some given N, if all its substrings of length N+1 are almost permutative (i.e. "ABCBACB", "ABCTABC", "CBACAB" -- hyper almost permutative strings for N=3).
Your task is to find the shortest hyper almost permutative string, containing permutative strings S1 and S2 as substrings for some given N. Strings S1 and S2 have the length N. The resulting string should be hyper almost permutative for the same given N.

Input
The first line of the input file contains the integer number N (2 <= N <= 26). The second line contains the permurtative string S1. The third line contains the permurtative string S2. You can assume that S1 and S2 are different.

Output
Write to the output file the answer for the problem. If there are several possible answers, output any of them.

Sample test(s)

Input
3
ABC
ACB

Output
ABCACB
Author:	Andrew V. Lazarev
Resource:	ACM ICPC 2004-2005, NEERC, Southern Subregional Contest
Date:	Saratov, October 7, 2004

<|response|>
## 1. Abridged Problem Statement

Given `N` and two different permutations `S1`, `S2` of the first `N` uppercase letters, construct the shortest string that:

- contains both `S1` and `S2` as substrings;
- is **hyper almost permutative**, meaning every substring of length `N + 1` can become a permutation of the first `N` letters after deleting exactly one character.

If several shortest strings exist, output any one.

Constraints:

```text
2 <= N <= 26
```

---

## 2. Key Observations

### Observation 1: We only need to move between permutation windows

Call a substring of length `N` that is a permutation of the first `N` letters a **stable window**.

A shortest answer can be assumed to:

- start with either `S1` or `S2`;
- end when it first reaches the other permutation.

So the problem becomes:

> Starting from one permutation window, append as few characters as possible until another required permutation appears as a window.

We try both directions:

```text
S1 -> S2
S2 -> S1
```

and take the shorter result.

---

### Observation 2: Valid transition from one permutation window to another

Suppose the current stable window is:

```text
W = w1 w2 ... wn
```

If we append `wp`, then the current length `N + 1` substring has one duplicate `wp`, so it is almost permutative.

After that, the following characters are forced:

```text
w1, w2, ..., w(p-1)
```

After appending these `p` characters total, the new stable window becomes:

```text
w(p+1) ... wn wp w1 ... w(p-1)
```

Example:

```text
W = ABC
p = 2

append: B A
new stable window: CBA
```

So every useful transition is determined by an index `p`, costs `p`, and transforms the current permutation window.

---

### Observation 3: Virtual zero model

Represent a stable window

```text
w1 w2 ... wn
```

as a cycle with a virtual symbol `0` before it:

```text
0 w1 w2 ... wn
```

Positions are considered cyclically, with cycle length `N + 1`.

Choosing transition `p` is equivalent to moving/swapping the virtual `0` clockwise by distance `p`.

The cost of the move is exactly `p`.

Therefore, the problem becomes:

> Transform one cyclic arrangement into another using swaps with `0`, minimizing the total clockwise distance.

Since `S2` can appear with the virtual zero inserted anywhere around it, we try all `N + 1` cyclic rotations of:

```text
0 + S2
```

---

## 3. Full Solution Approach

For a fixed start arrangement `a` and target arrangement `b`, both of length `N + 1`, containing values:

```text
0, 1, 2, ..., N
```

where `0` is the virtual symbol, define:

```text
perm[i] = target position of value currently at position i
```

This is a permutation of positions `0..N`.

We decompose `perm` into cycles.

---

### Cycle containing zero

Suppose the cycle containing zero is:

```text
0 -> p1 -> p2 -> ... -> pt -> 0
```

To fix it using swaps with zero, we walk through it in reverse order:

```text
0, pt, p(t-1), ..., p1
```

Each step has cost equal to clockwise distance between consecutive positions.

After this, zero ends at position `perm[0]`.

---

### Cycles not containing zero

Let:

```text
z = perm[0]
```

This is the current position of zero after fixing the zero-cycle.

For another cycle:

```text
c0 -> c1 -> ... -> c(k-1) -> c0
```

zero must:

1. enter the cycle from `z`;
2. traverse the cycle in reverse order;
3. return to `z`.

For some starting index `s`, the walk is:

```text
z -> cs -> c(s-1) -> ... -> c(s+1) -> z
```

We choose `s` so that this walk has minimum cost.

Geometrically, this is achieved by choosing an edge of the cycle whose clockwise arc does not contain `z`.

---

### Trying all possibilities

We try:

1. starting from `S1`, targeting `S2`;
2. starting from `S2`, targeting `S1`;

and for each direction, all `N + 1` rotations of the target cyclic arrangement.

For each case, we compute the minimum move sequence.

Finally, we reconstruct the actual answer:

1. output the starting permutation;
2. for every move of distance `p`, append:

```text
a[p], a[1], ..., a[p-1]
```

3. update the current stable window.

Complexity:

```text
O(N^2)
```

Since `N <= 26`, this is easily fast enough.

---

## 4. C++ Implementation with Detailed Comments

```cpp
#include <bits/stdc++.h>

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

int n;
string s1, s2;
array<int, 27> a{}, b{};
vector<int> move_costs;

void read() { cin >> n >> s1 >> s2; }

int push_step(int from, int to) {
    int d = (to - from + n + 1) % (n + 1);
    move_costs.push_back(d);
    return d;
}

int compute_cost() {
    move_costs.clear();
    int total = 0;
    array<int, 27> pos_in_b{}, perm{};
    for(int i = 0; i <= n; i++) {
        pos_in_b[b[i]] = i;
    }

    for(int i = 0; i <= n; i++) {
        perm[i] = pos_in_b[a[i]];
    }

    array<bool, 27> visited{};
    for(int i = 0; i <= n; i++) {
        if(visited[i]) {
            continue;
        }

        visited[i] = true;
        if(perm[i] == i) {
            continue;
        }

        vector<int> cycle = {i};
        for(int x = perm[i]; x != i; x = perm[x]) {
            cycle.push_back(x);
            visited[x] = true;
        }

        int cnt = (int)cycle.size();
        if(i == 0) {
            reverse(cycle.begin() + 1, cycle.end());
            for(int j = 1; j < cnt; j++) {
                total += push_step(cycle[j - 1], cycle[j]);
            }
        } else {
            int start = 0;
            for(int j = 0; j < cnt; j++) {
                int x = cycle[j], y = cycle[(j + 1) % cnt];
                bool zero_outside = x < y && (perm[0] < x || perm[0] > y);
                bool zero_inside_wrap = y < perm[0] && perm[0] < x;
                if(zero_outside || zero_inside_wrap) {
                    start = j;
                }
            }

            rotate(cycle.begin(), cycle.begin() + start, cycle.end());
            reverse(cycle.begin() + 1, cycle.end());
            total += push_step(perm[0], cycle[0]);
            for(int j = 1; j < cnt; j++) {
                total += push_step(cycle[j - 1], cycle[j]);
            }

            total += push_step(cycle.back(), perm[0]);
        }
    }

    return total;
}

void apply_move(int p) {
    array<int, 27> next_a{};
    for(int i = p + 1; i <= n; i++) {
        next_a[i - p] = a[i];
    }
    next_a[n - p + 1] = a[p];
    for(int i = 1; i < p; i++) {
        next_a[n - p + 1 + i] = a[i];
    }
    for(int i = 1; i <= n; i++) {
        a[i] = next_a[i];
    }
}

void solve() {
    // Assume WLOG the output string T starts with S1 (we also try the
    // S2-first ordering and pick the shorter). The first N characters of T
    // are S1. Every window of length N+1 in T must be almost-permutative
    // (one duplicate, one missing), so each new character is forced to be
    // the one that just left the previous window of length N, until the
    // window becomes a full permutation again.
    //
    // Concretely, if the current full-permutation window is W = w_1..w_n,
    // the next "stable" window is produced by choosing a split point
    // p in {1..n-1}, appending w_p, w_1, w_2, ..., w_{p-1} (cost = p new
    // characters), and the new window becomes w_{p+1}..w_n w_p w_1..w_{p-1}.
    //
    // Prepend a virtual symbol 0 at position 0 and treat positions
    // 0..n as a cycle of length n+1. A move with split p is equivalent to
    // swapping the element at position p with the 0 (the cost p is exactly
    // the clockwise distance from 0's current position to p). The goal is
    // to transform the permutation of S1 into some cyclic rotation of the
    // permutation of S2 with minimum total swap distance.
    //
    // perm[i] is the position where the value currently at position i in a
    // needs to land in b. We can show that we should fix cycles independently,
    // as otherwise we will just waste more operations that would merge the
    // cycles, increasing the overall cost. Now let's consider the cycles
    // themselves:
    //
    //   - First the cycle containing 0. Write it in perm-order as
    //     C_0 = (0 -> p_1 -> p_2 -> ... -> p_t -> 0). We resolve it by
    //     walking 0 through positions q_0 = 0, q_1, q_2, ..., q_m, where
    //     each step is a swap with 0. Such a walk has a fixed value-transport
    //     effect: the value originally at q_i ends up at q_{i-1}, and 0 ends
    //     at q_m. We need the value at each q_i to land at perm[q_i], so we
    //     need perm[q_i] = q_{i-1}, i.e., q_i must come AFTER q_{i-1} in the
    //     cycle's perm-order. So we walk C_0 in REVERSE perm-order:
    //
    //         q_0 = 0, q_1 = p_t, q_2 = p_{t-1}, ..., q_t = p_1.
    //
    //     The cost is the sum of clockwise step distances along that reversed
    //     walk, and after this phase 0 sits at p_1 = perm[0]. (If perm[0] = 0
    //     the 0-cycle is trivial and 0 stays at position 0.)
    //
    //   - Then every other cycle. Let C = (c_0 -> c_1 -> ... -> c_{k-1} -> c_0)
    //     be a non-zero cycle, and let z := perm[0] be the position where 0
    //     currently sits (either 0, or the spot left by the 0-cycle phase).
    //     z is not in C (distinct cycles are disjoint), so 0 has to take a
    //     round trip: leave z, traverse C, return to z. Same reverse-walk
    //     reasoning as above: starting at q_0 = z, pick an entry index s and
    //     walk
    //
    //         z -> c_s -> c_{s-1} -> ... -> c_{s+1} -> z   (indices mod k)
    //
    //     The k middle swaps transport the cycle's values one perm-step
    //     forward, and the final swap z <-> last position brings z's value
    //     (which had been displaced by the first swap) back home. So z ends
    //     up holding what it started with, and every value in C lands where
    //     perm sends it.
    //
    //     Let W = sum_{j} d(c_j, c_{(j+1) mod k}) be the total clockwise
    //     length of C walked in cycle-order (an invariant of C, not of s).
    //     Telescoping the seven-term walk above, its cost is
    //
    //         d(z, c_s)  +  (W - d(c_{s+1}, c_s))  +  d(c_{s+1}, z),
    //
    //     and this collapses to exactly W iff z lies on the clockwise arc
    //     from c_{s+1} back to c_s. Equivalently, z is NOT on the open
    //     clockwise arc c_s -> c_{s+1}. Such an s always exists: take c_s as
    //     the first cycle vertex met going clockwise from z. By construction
    //     no cycle vertex lies in the open arc (z, c_s), so c_{s+1} (which is
    //     != c_s since k >= 2) must sit clockwise past c_s, and the edge
    //     c_s -> c_{s+1} cannot wrap back around to contain z.
    //
    // Try every cyclic rotation of b (where 0 ends up sitting), both
    // S1-first and S2-first, take the cheapest, then replay the swaps to
    // emit the answer.

    a[0] = b[0] = 0;
    for(int i = 0; i < n; i++) {
        a[i + 1] = s1[i] - 'A' + 1;
        b[i + 1] = s2[i] - 'A' + 1;
    }

    int best_dir = 0, best_rot = 0, best_cost = INT_MAX;
    for(int dir = 0; dir < 2; dir++) {
        for(int r = 0; r <= n; r++) {
            int c = compute_cost();
            if(c < best_cost) {
                best_cost = c;
                best_dir = dir;
                best_rot = r;
            }
            rotate(b.begin(), b.begin() + 1, b.begin() + n + 1);
        }

        swap(a, b);
    }

    if(best_dir == 1) {
        swap(a, b);
    }

    rotate(b.begin(), b.begin() + best_rot, b.begin() + n + 1);
    compute_cost();

    string result;
    for(int i = 1; i <= n; i++) {
        result += (char)('A' + a[i] - 1);
    }

    for(int p: move_costs) {
        if(p == 0) {
            continue;
        }
        result += (char)('A' + a[p] - 1);
        for(int i = 1; i < p; i++) {
            result += (char)('A' + a[i] - 1);
        }
        apply_move(p);
    }

    cout << result << '\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();
        solve();
    }

    return 0;
}
```

---

## 5. Python Implementation with Detailed Comments

```python
import sys


def clockwise_distance(frm, to, n):
    """
    Clockwise distance from position frm to position to
    on a cycle of length n + 1.
    """
    return (to - frm + n + 1) % (n + 1)


def compute_cost(a, b, n):
    """
    Compute the minimum cost to transform cyclic arrangement a into b.

    a and b are lists of length n + 1.
    Position 0 is the virtual zero.
    Values 1..n are letters A..Z encoded as integers.

    Returns:
        total_cost, moves
    """

    moves = []
    total = 0

    # pos_in_b[value] = position where this value should be in target b.
    pos_in_b = [0] * (n + 1)

    for i in range(n + 1):
        pos_in_b[b[i]] = i

    # perm[i] = target position of value currently at position i.
    perm = [0] * (n + 1)

    for i in range(n + 1):
        perm[i] = pos_in_b[a[i]]

    def push_step(frm, to):
        """
        Record one move from frm to to and return its cost.
        """
        d = clockwise_distance(frm, to, n)
        moves.append(d)
        return d

    visited = [False] * (n + 1)

    # Decompose perm into cycles.
    for i in range(n + 1):
        if visited[i]:
            continue

        visited[i] = True

        # Fixed point.
        if perm[i] == i:
            continue

        cycle = [i]
        x = perm[i]

        while x != i:
            cycle.append(x)
            visited[x] = True
            x = perm[x]

        cnt = len(cycle)

        # Case 1: cycle containing zero.
        if i == 0:
            # Walk through the cycle in reverse order, keeping zero first.
            cycle = [cycle[0]] + list(reversed(cycle[1:]))

            for j in range(1, cnt):
                total += push_step(cycle[j - 1], cycle[j])

        # Case 2: cycle not containing zero.
        else:
            z = perm[0]

            start = 0

            # Choose a good edge where z is outside the open clockwise arc.
            for j in range(cnt):
                x = cycle[j]
                y = cycle[(j + 1) % cnt]

                good = False

                if x < y:
                    # Non-wrapping arc x -> y.
                    if z < x or z > y:
                        good = True
                else:
                    # Wrapping arc x -> ... -> n -> 0 -> ... -> y.
                    if y < z < x:
                        good = True

                if good:
                    start = j

            # Rotate cycle so chosen start is first.
            cycle = cycle[start:] + cycle[:start]

            # Traverse remaining vertices in reverse order.
            cycle = [cycle[0]] + list(reversed(cycle[1:]))

            # Enter the cycle.
            total += push_step(z, cycle[0])

            # Traverse the cycle.
            for j in range(1, cnt):
                total += push_step(cycle[j - 1], cycle[j])

            # Return to z.
            total += push_step(cycle[-1], z)

    return total, moves


def apply_move(a, p, n):
    """
    Apply one real move of length p to current stable window a[1..n].

    Appended characters are:
        a[p], a[1], ..., a[p - 1]

    New stable window becomes:
        a[p + 1], ..., a[n], a[p], a[1], ..., a[p - 1]
    """

    nxt = [0] * (n + 1)

    # Elements after p go to the front.
    for i in range(p + 1, n + 1):
        nxt[i - p] = a[i]

    # Element p follows.
    nxt[n - p + 1] = a[p]

    # Elements before p follow.
    for i in range(1, p):
        nxt[n - p + 1 + i] = a[i]

    return nxt


def solve():
    data = sys.stdin.read().strip().split()

    n = int(data[0])
    s1 = data[1]
    s2 = data[2]

    # Encode permutations.
    # 0 is the virtual symbol.
    a = [0] + [ord(ch) - ord('A') + 1 for ch in s1]
    b = [0] + [ord(ch) - ord('A') + 1 for ch in s2]

    best_cost = 10**9
    best_dir = 0
    best_rot = 0

    # Try both directions.
    for direction in range(2):
        # Try all rotations of the target arrangement.
        for r in range(n + 1):
            cost, _ = compute_cost(a, b, n)

            if cost < best_cost:
                best_cost = cost
                best_dir = direction
                best_rot = r

            # Rotate target left by one position.
            b = b[1:] + b[:1]

        # Swap direction.
        a, b = b, a

    # Restore chosen direction.
    if best_dir == 1:
        a, b = b, a

    # Apply chosen target rotation.
    b = b[best_rot:] + b[:best_rot]

    # Recompute the moves for the chosen optimal case.
    _, moves = compute_cost(a, b, n)

    result = []

    # Start with the chosen starting permutation.
    for i in range(1, n + 1):
        result.append(chr(ord('A') + a[i] - 1))

    # Replay every move.
    for p in moves:
        if p == 0:
            continue

        # Append a[p].
        result.append(chr(ord('A') + a[p] - 1))

        # Append a[1], ..., a[p - 1].
        for i in range(1, p):
            result.append(chr(ord('A') + a[i] - 1))

        # Update current stable window.
        a = apply_move(a, p, n)

    print(''.join(result))


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