#include <stdio.h>
#include <time.h>
int cache[35][35];

void initialized_cache(){
    for (int i = 0; i < 35; i++){
        for (int j = 0; j < 35; j++){
            cache[i][j] = -1;
        }
    }
}

int is_valid_char(char c) {
    if (c >= 'A' && c <= 'Z') return 1;
    if (c >= 'a' && c <= 'z') return 1;
    if (c >= '0' && c <= '9') return 1;

    char valid_specials[] = " ',.~\\<>/?!@#$%^&*()_+ {}[]:;|";
    for (int i = 0; valid_specials[i] != '\0'; i++) {
        if (c == valid_specials[i]) return 1;
    }

    return 0;
}

void input_string(char *string, int *len_string){
    char char_input;
    for (int i = 0; i < 34; i++){
        if ((char_input = getchar()) == '\n' || char_input == EOF){
            string[i] = '\0';
            return;
        }
        if (!is_valid_char(char_input)) {
            printf("incorrect msg");
            string[i] = '\0';
            return;
        }
        string[i] = char_input;
        (*len_string)++;
    }
}

int search_max_len_polindromic(char *string, int start, int end){
    if (start >= end) {
        if (start == end) {
            return 1;
        }
        return 0;
    }
    if (cache[start][end] != -1){
        return cache[start][end];
    }
    if (string[start] == string[end]){
        cache[start][end] = 2 + search_max_len_polindromic(string, start + 1, end - 1);
    }
    else{
        int right = search_max_len_polindromic(string, start, end - 1);
        int left = search_max_len_polindromic(string, start + 1, end);
        cache[start][end] = (right > left) ? right : left;
    }
    return cache[start][end];
}

void restore_polindromic(char *string, int start, int end, char *result, int *right, int *left, int *used){
    if (start > end){
        return;
    }
    if (start == end){
        result[*left] = string[start];
        used[start] = 1;
        return;
    }
    if (string[start] == string[end]){
        result[*left] = string[start];
        result[*right] = string[end];
        used[start] = 1;
        used[end] = 1;
        (*left)++;
        (*right)--;
        restore_polindromic(string, start + 1, end - 1, result, right, left, used);
    }
    else if (cache[start + 1][end] > cache[start][end - 1]){;
            restore_polindromic(string, start + 1, end - 1, result, right, left, used);
    }
    else{
         restore_polindromic(string, start, end - 1, result, right, left, used);
    }
}

int main(){
    char string[35];
    int len_string = 0;
    char result[35] = {0};
    int used[35] = {0};
    input_string(string, &len_string);
    initialized_cache();
    search_max_len_polindromic(string, 0, len_string - 1);
    int left = 0;
    int right = cache[0][len_string - 1] - 1;
    restore_polindromic(string, 0, len_string - 1, result, &right, &left, used);
    result[len_string] = '\0';
    used[len_string] = '\0';
    printf("%s\n", result);
    for (int i = 0; i < len_string; i++){
        if (!used[i]){
            printf("%d - %c, ", i + 1, string[i]);
        }
    }
    return 0;
}