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

Appending a character outside the first `N` letters can only create a useless loop that eventually returns to the same permutation, so it is never useful in a shortest answer.

---

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

int n;
string s1, s2;

// Cyclic arrangements.
// Position 0 is the virtual symbol 0.
// Positions 1..n store letters encoded as 1..n.
array<int, 27> a{}, b{};

// Sequence of move lengths for the currently computed transformation.
vector<int> moves;

/*
    Clockwise distance from position from to position to
    on a cycle of length n + 1.
*/
int clockwise_distance(int from, int to) {
    return (to - from + n + 1) % (n + 1);
}

/*
    Record one move and return its cost.
*/
int push_step(int from, int to) {
    int d = clockwise_distance(from, to);
    moves.push_back(d);
    return d;
}

/*
    Compute the minimum cost to transform cyclic arrangement a into b.

    Also fills the global vector moves with the corresponding move lengths.
*/
int compute_cost() {
    moves.clear();

    int total = 0;

    array<int, 27> pos_in_b{}, perm{};

    // pos_in_b[value] = position of value in target arrangement b.
    for (int i = 0; i <= n; i++) {
        pos_in_b[b[i]] = i;
    }

    // perm[i] = target position of the value currently at position i.
    for (int i = 0; i <= n; i++) {
        perm[i] = pos_in_b[a[i]];
    }

    array<bool, 27> visited{};

    // Decompose perm into cycles.
    for (int i = 0; i <= n; i++) {
        if (visited[i]) {
            continue;
        }

        visited[i] = true;

        // Fixed point: already correct.
        if (perm[i] == i) {
            continue;
        }

        vector<int> cycle;
        cycle.push_back(i);

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

        int cnt = (int)cycle.size();

        /*
            Case 1: cycle containing zero.

            Since positions are processed in increasing order, if zero belongs
            to this cycle, then i == 0.
        */
        if (i == 0) {
            // Walk through the cycle in reverse order, keeping 0 first.
            reverse(cycle.begin() + 1, cycle.end());

            for (int j = 1; j < cnt; j++) {
                total += push_step(cycle[j - 1], cycle[j]);
            }
        }

        /*
            Case 2: cycle not containing zero.

            Zero currently sits at position perm[0].
            We enter the cycle, traverse it in reverse order, and return.
        */
        else {
            int z = perm[0];

            int start = 0;

            /*
                Choose an edge cycle[j] -> cycle[j + 1] such that z is not
                inside the open clockwise arc from cycle[j] to cycle[j + 1].
            */
            for (int j = 0; j < cnt; j++) {
                int x = cycle[j];
                int y = cycle[(j + 1) % cnt];

                bool good = false;

                if (x < y) {
                    // Non-wrapping arc: x -> y.
                    // z is outside if z < x or z > y.
                    if (z < x || z > y) {
                        good = true;
                    }
                } else {
                    // Wrapping arc: x -> ... -> n -> 0 -> ... -> y.
                    // z is outside iff y < z < x.
                    if (y < z && z < x) {
                        good = true;
                    }
                }

                if (good) {
                    start = j;
                }
            }

            // Rotate cycle so that chosen start is first.
            rotate(cycle.begin(), cycle.begin() + start, cycle.end());

            // Traverse remaining cycle vertices in reverse order.
            reverse(cycle.begin() + 1, cycle.end());

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

            // Traverse the cycle.
            for (int j = 1; j < cnt; j++) {
                total += push_step(cycle[j - 1], cycle[j]);
            }

            // Return to z.
            total += push_step(cycle.back(), z);
        }
    }

    return total;
}

/*
    Apply one move of length p to the current stable window a[1..n].

    If current window is:

        a[1], a[2], ..., a[n]

    then appending:

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

    creates the new stable window:

        a[p + 1], ..., a[n], a[p], a[1], ..., a[p - 1]
*/
void apply_move(int p) {
    array<int, 27> next_a{};

    // Elements after p move to the front.
    for (int i = p + 1; i <= n; i++) {
        next_a[i - p] = a[i];
    }

    // Element p follows.
    next_a[n - p + 1] = a[p];

    // Elements before p follow.
    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];
    }
}

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

    cin >> n >> s1 >> s2;

    // Initial arrangements: 0 + permutation.
    a[0] = 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_cost = INT_MAX;
    int best_dir = 0;
    int best_rot = 0;

    /*
        Try both directions.

        dir = 0: start from S1, target S2
        dir = 1: start from S2, target S1
    */
    for (int dir = 0; dir < 2; dir++) {
        // Try all cyclic rotations of the target arrangement.
        for (int r = 0; r <= n; r++) {
            int cost = compute_cost();

            if (cost < best_cost) {
                best_cost = cost;
                best_dir = dir;
                best_rot = r;
            }

            rotate(b.begin(), b.begin() + 1, b.begin() + n + 1);
        }

        // Swap direction.
        swap(a, b);
    }

    /*
        After the loops, a and b are back to their original orientation.

        If best_dir == 1, the answer should start from S2 instead of S1.
    */
    if (best_dir == 1) {
        swap(a, b);
    }

    // Apply the best target rotation.
    rotate(b.begin(), b.begin() + best_rot, b.begin() + n + 1);

    // Recompute moves for the chosen optimal configuration.
    compute_cost();

    string answer;

    // Start answer with the chosen initial permutation.
    for (int i = 1; i <= n; i++) {
        answer += char('A' + a[i] - 1);
    }

    // Replay moves and append the forced characters.
    for (int p : moves) {
        if (p == 0) {
            continue;
        }

        // Append a[p].
        answer += char('A' + a[p] - 1);

        // Append a[1], ..., a[p - 1].
        for (int i = 1; i < p; i++) {
            answer += char('A' + a[i] - 1);
        }

        // Update current stable window.
        apply_move(p);
    }

    cout << answer << '\n';

    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()
```