use std::io::BufRead;
use std::str::FromStr;
use std::fmt::Debug;

struct Scanner<R: BufRead> {
    buf_reader: R,
}

impl<R: BufRead> Scanner<R> {
    fn new(buf_reader: R) -> Self {
        Scanner {buf_reader: buf_reader}
    }
    fn read_line<T>(&mut self) -> Vec<T> where T: FromStr, <T as FromStr>::Err: Debug {
        let mut line = String::new();
        self.buf_reader.read_line(&mut line).unwrap();
        line.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()
    }
    fn read_single_value<T>(&mut self) -> T where T: FromStr, <T as FromStr>::Err: Debug {
        let mut line = String::new();
        self.buf_reader.read_line(&mut line).unwrap();
        let sv: Vec<&str> = line.trim().split_whitespace().collect();
        sv[0].parse::<T>().unwrap()
    }
    fn read_line0(&mut self) -> Vec<String> {
        let mut line: String = String::new();
        self.buf_reader.read_line(&mut line).unwrap();
        line.trim().split_whitespace().map(|c| c.to_string()).collect()
    }
}

struct Card {
    suit: char,
    num:  u32,
}

fn main() {
    let stdin = std::io::stdin();
    let mut scanner = Scanner::new(stdin.lock());
    let n = scanner.read_single_value::<usize>();
    let mut seq = scanner.read_line0();
    let mut c0: Vec<Card> = vec![];
    let mut c1: Vec<Card> = vec![];
    let mut c2: Vec<Card> = vec![];
    for i in 0..seq.len() {
        let mut char_indices = seq[i].char_indices();
        let suit: char = char_indices.next().unwrap().1;
        let num:  u32  = char_indices.next().unwrap().1.to_digit(10).unwrap();
        c0.push(Card{suit: suit, num: num});
        c1.push(Card{suit: suit, num: num});
        c2.push(Card{suit: suit, num: num});
    }

    bubble_sort(&mut c1);
    selection_sort(&mut c2);
    let st1 = check_stable(&c0, &c1);
    let st2 = check_stable(&c0, &c2);
    print_card(&c1, st1);
    print_card(&c2, st2);
}

fn print_card(c: &Vec<Card>, st: bool) {
    let mut s = String::new();
    s.push(c[0].suit); s.push_str(&c[0].num.to_string());
    for i in 1..c.len() {
        s.push(' '); s.push(c[i].suit); s.push_str(&c[i].num.to_string());
    }
    println!("{}", s);
    if st {
        println!("Stable");
    }
    else {
        println!("Not stable");
    }
} 

fn bubble_sort(c: &mut Vec<Card>) {
    let n = c.len();
    for i in 0..n {
        for j0 in i..n-1 {
           let j = n + i - 1 - j0;
           if c[j].num < c[j-1].num {
               c.swap(j, j-1);
           }
        }
    }
}

fn selection_sort(c: &mut Vec<Card>) {
    let n = c.len();
    for i in 0..n {
        let mut min_i = i;
        for j in i..n {
           if c[j].num < c[min_i].num {
               min_i = j;
           }
        }
        c.swap(i, min_i);
    }
}

fn check_stable(c0: &Vec<Card>, c: &Vec<Card>) -> bool {
    let mut left = -1;
    let mut right = -1;
    for i in 1..c.len() {
        if c[i].num != c[i-1].num {
            left = -1;
            continue;
        }
        for j in 0..c0.len() {
            if c0[j].num == c[i].num && c0[j].suit == c[i].suit {
                right = j as i32;
                if left >= 0 {
                    break;
                }
            }
            if c0[j].num == c[i-1].num && c0[j].suit == c[i-1].suit {
                left = j as i32;
                if right >= 0 {
                    break;
                }
            }
        }
        if left > right {
            return false;
        }
        left = right;
        right = -1;
    }
    true
}


Measured memory_bytes: 5040