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

142. Keyword

time limit per test: 0.5 sec.
memory limit per test: 16384 KB


Kevin has invented a new algorithm to crypt and decrypt messages, which he thinks is unbeatable. The algorithm uses a very large key-string, out of which a keyword is found out after applying the algorithm. Then, based on this keyword, the message is easily crypted or decrypted. So, if one would try to decrypt some messages crypted with this algorithm, then knowing the keyword would be enough. Someone has found out how the keyword is computed from the large key-string, but because he is not a very experienced computer programmer, he needs your help. The key-string consists of N characters from the set {'a','b'}. The keyword is the shortest non-empty string made up of the letters 'a' and 'b', which is not contained as a contiguous substring (also called subsequence) inside the key-string. It is possible that more than one such string exists, but the algorithm is designed in such a way that any of these strings can be used as a keyword. Given the key-string, your task is to find one keyword.


Input

The first line contains the integer number N, the number of characters inside the key-string (1 <= N <= 500 000). The next line contains N characters from the set {'a','b'} representing the string.


Output

The first line of output should contain the number of characters of the keyword. The second line should contain the keyword.


Sample Input

11
aabaaabbbab
Sample Output

4
aaaa
Author	: Mugurel Ionut Andreica
Resource	: SSU::Online Contester Fall Contest #2
Date	: Fall 2002

<|response|>
1. Abridged Problem Statement
You are given a binary string S of length N (each character is 'a' or 'b'). Find the shortest non-empty binary string T over {'a','b'} that does **not** appear anywhere in S as a contiguous substring. Output the length of T and one such T.

2. Key Observations
- For any length L, there are exactly 2^L possible binary strings of length L, but S has only (N−L+1) substrings of length L.
- As soon as 2^L > (N−L+1), the pigeonhole principle guarantees at least one length-L string is missing from S.
- The smallest L satisfying 2^L > N−L+1 is O(log₂N), so L will be at most about 20 when N≤5·10^5.
- We can detect which length-L strings appear by a single O(N) scan using a rolling bitmask (window) of width L over S.

3. Full Solution Approach
1. Map 'a'→0 and 'b'→1 so that each substring of length L corresponds to an integer mask in [0,2^L).
2. For L = 1, 2, 3, …:
   a. Allocate a count array of size 2^L, initialized to zero.
   b. Compute the integer mask of the first L characters of S by shifting and OR’ing bits. Increment cnt[mask].
   c. Slide a window of width L from position L to N–1:
      - Update `mask = ((mask << 1) & ((1<<L)-1)) | bit(S[i])`.
      - Increment cnt[mask].
   d. Scan masks 0..2^L−1; if any `cnt[m]` is zero, that mask corresponds to an absent substring.
   e. Reconstruct the missing substring by reading the bits of m from most significant to least, mapping 0→'a', 1→'b'. Output L and the string, then terminate.
3. This runs in O(N·L_max + 2^L_max) time where L_max ≈ log₂N.

4. C++ Implementation
```cpp
#include <bits/stdc++.h>
// #include <coding_library/strings/suffix_automaton.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;
};

int n;
string s;

void read() { cin >> n >> s; }

void solve() {
    // The shortest absent substring has length at most ~20 since a string of
    // length n contains at most n distinct substrings of any given length, so
    // once 2^len > n some length-len word must be missing. We try increasing
    // lengths len = 1, 2, ...; for each we slide a window over the key-string
    // encoding the current window as a binary mask (a -> 0, b -> 1) and tally
    // cnt[mask] for every length-len occurrence. The first mask with count
    // zero is an absent word; we print it most-significant bit first.

    vector<int> cnt;
    for(int len = 1;; len++) {
        cnt.assign(1 << len, 0);
        int mask = 0;
        for(int i = 0; i < len; i++) {
            mask = (mask << 1) | (s[i] - 'a');
        }
        cnt[mask]++;
        for(int i = len; i < n; i++) {
            mask = ((mask << 1) & ((1 << len) - 1)) | (s[i] - 'a');
            cnt[mask]++;
        }

        for(int i = 0; i < (1 << len); i++) {
            if(cnt[i] == 0) {
                cout << len << '\n';
                for(int j = len - 1; j >= 0; j--) {
                    cout << (char)((i >> j & 1) + 'a');
                }
                return;
            }
        }
    }
}

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

def find_shortest_absent(S):
    n = len(S)
    # Convert 'a'/'b' into 0/1 for fast bit operations
    bits = [ord(c) - ord('a') for c in S]

    L = 1
    while True:
        size = 1 << L                  # total possible patterns of length L
        seen = [False] * size

        # initial mask from bits[0..L-1]
        mask = 0
        for i in range(L):
            mask = (mask << 1) | bits[i]
        seen[mask] = True

        trim = size - 1                # mask with L ones: to discard overflow bits

        # slide the window
        for i in range(L, n):
            mask = ((mask << 1) & trim) | bits[i]
            seen[mask] = True

        # look for the first unseen pattern
        for m in range(size):
            if not seen[m]:
                # reconstruct the string for mask m
                res_chars = []
                for bit in reversed(range(L)):
                    b = (m >> bit) & 1
                    res_chars.append(chr(b + ord('a')))
                return L, "".join(res_chars)

        L += 1  # increase length and repeat

if __name__ == "__main__":
    data = sys.stdin.read().split()
    n = int(data[0])
    s = data[1].strip()
    length, keyword = find_shortest_absent(s)
    print(length)
    print(keyword)
```

Explanation of Key Steps:
- We iterate L from 1 upward until we find a missing substring.
- A boolean array `seen` of size 2^L tracks which length-L patterns occur in S.
- We maintain a rolling integer `mask` representing the current window of L bits.
- Each time we move the window by one character, we shift `mask` left by one, mask off the top bit, and OR in the new bit.
- After scanning S, the first index `m` in `seen` that remains False encodes a missing substring; its binary digits map directly to 'a'/'b'.
