<|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 boolean array `seen` of size 2^L, initialized to false.  
   b. Compute the integer mask of the first L characters of S by shifting and OR’ing bits. Mark `seen[mask] = true`.  
   c. Slide a window of width L from position L to N–1:  
      - Update `mask = ((mask << 1) & ((1<<L)-1)) | bit(S[i])`.  
      - Mark `seen[mask] = true`.  
   d. Scan masks 0..2^L−1; if any `seen[m]` is false, 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 with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

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

    int N;
    string S;
    cin >> N >> S;

    // Try every length L starting from 1
    for (int L = 1; ; L++) {
        int total = 1 << L;              // number of possible masks of length L
        vector<bool> seen(total, false);

        // Build mask for the first window S[0..L-1]
        int mask = 0;
        for (int i = 0; i < L; i++) {
            // shift left and add 0 for 'a', 1 for 'b'
            mask = (mask << 1) | (S[i] - 'a');
        }
        seen[mask] = true;

        // Prepare a bitmask of L ones to trim upper bits
        int trim = total - 1;  // (1<<L) - 1

        // Slide the window over the rest of the string
        for (int i = L; i < N; i++) {
            // shift left, drop the bit that falls off, add new bit
            mask = ((mask << 1) & trim) | (S[i] - 'a');
            seen[mask] = true;
        }

        // Check for the first unseen mask
        for (int m = 0; m < total; m++) {
            if (!seen[m]) {
                // Found absent substring of length L
                cout << L << "\n";
                // Reconstruct the substring from mask m
                for (int bit = L - 1; bit >= 0; bit--) {
                    // extract the bit-th bit (0=MSB) of m
                    char c = ((m >> bit) & 1) + 'a';
                    cout << c;
                }
                cout << "\n";
                return 0;
            }
        }
        // Otherwise, no missing substring of length L; try L+1
    }
    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'.