use std::io::{self, BufRead, BufWriter};
use std::io::Write;
use std::str;
use std::cmp::{max,min};

/// https://github.com/EbTech/rust-algorithms/blob/master/src/scanner.rs
pub struct Scanner<R> {
    reader: R,
    buffer: Vec<String>,
}

impl<R: io::BufRead> Scanner<R> {
    pub fn new(reader: R) -> Self {
        Self {
            reader,
            buffer: vec![],
        }
    }

    pub fn token<T: str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buffer.pop() {
                return token.parse().ok().expect("Failed parse");
            }
            let mut input = String::new();
            self.reader.read_line(&mut input).expect("Failed read");
            self.buffer = input.split_whitespace().rev().map(String::from).collect();
        }
    }
}

// https://github.com/EbTech/rust-algorithms/blob/master/src/rng.rs
pub type SmallRng = Xoshiro256PlusPlus;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Xoshiro256PlusPlus {
    s: [u64; 4],
}

impl Xoshiro256PlusPlus {
    /// Construct a new RNG from a 64-bit seed.
    pub fn new(mut state: u64) -> Self {
        const PHI: u64 = 0x9e3779b97f4a7c15;
        let mut seed = <[u64; 4]>::default();
        for chunk in &mut seed {
            state = state.wrapping_add(PHI);
            let mut z = state;
            z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
            z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
            z = z ^ (z >> 31);
            *chunk = z;
        }
        Self { s: seed }
    }

    /// Generate a random `u32`.
    #[inline]
    pub fn next_u32(&mut self) -> u32 {
        (self.next_u64() >> 32) as u32
    }

    /// Generate a random `u64`.
    #[inline]
    pub fn next_u64(&mut self) -> u64 {
        let result_plusplus = self.s[0]
            .wrapping_add(self.s[3])
            .rotate_left(23)
            .wrapping_add(self.s[0]);

        let t = self.s[1] << 17;

        self.s[2] ^= self.s[0];
        self.s[3] ^= self.s[1];
        self.s[1] ^= self.s[2];
        self.s[0] ^= self.s[3];

        self.s[2] ^= t;

        self.s[3] = self.s[3].rotate_left(45);

        result_plusplus
    }
}

fn send<T: Write>(out: &mut BufWriter<T>, v: u8) {
    let c = if v == 0 {
        'K'
    } else if v == 1 {
        'N'
    } else if v == 2 {
        'P'
    } else {
        panic!("Invalid v");
    };

    writeln!(out, "{}", c).unwrap();
    out.flush().unwrap();
}

fn recv<S: BufRead>(scan: &mut Scanner<S>) -> u8{
    let v = scan.token::<String>().chars().map(|ch| if ch == 'K' {
        0
    } else if ch == 'N' {
        1
    } else {
        2
    }).collect::<Vec<_>>();
    return v[0];
}

fn interact<S: BufRead, T: Write>(scan: &mut Scanner<S>, out: &mut BufWriter<T>, v: u8) -> (u8, i32) {
    send(out, v);
    let res = recv(scan);
    let score_change  = ((res as i32) - (v as i32)).rem_euclid(3);
    return if score_change == 2 {
        (res, -1)
    } else {
        (res, score_change)
    }
}

fn xx(a: Vec<bool>, x: &Vec<u32>) -> Vec<bool> {
    a.into_iter().zip(x).map(|(a,b)| if b%2 == 0 {a} else {!a}).collect()
}

fn solve<S: BufRead, T: Write>(scan: &mut Scanner<S>, out: &mut BufWriter<T>, is_a: bool, n: usize, t: usize) {
    let mut rng = SmallRng::new(461278477410u64+(t as u64));
    let a_key = (0..n).map(|_| rng.next_u32()).collect::<Vec<_>>();
    let b_key = (0..n).map(|_| rng.next_u32()).collect::<Vec<_>>();
    

    let mine: Vec<bool> = scan.token::<String>().chars().map(|ch| ch == '1').collect();
    let mine = xx(mine, if is_a {&a_key} else {&b_key});


    let mut round = 0;
    let mut my_score  = 0;
    let mut last_draw = 0;

    let mut opp = mine.clone();

    let mut shared_me = 0usize;
    let mut known_op = 0usize;

    while shared_me < n || known_op < n {
        // eprintln!("{my_score} {shared_me} {known_op}");
        if my_score == 0 {
            let v;
            if shared_me == n {
                v = 0;
            } else {
                if mine[shared_me] == true {
                    v = 0;
                    shared_me += 1;
                } else if mine[shared_me] == false && (shared_me+1 == n || mine[shared_me+1] == false) {
                    v = 1;
                    shared_me += 2;
                } else {
                    v = 2;
                    shared_me += 2;
                }
                shared_me = min(shared_me, n);
            }
        
            let (w, score_change) = interact(scan, out, v);
            
            // eprintln!("v {v} res {w} score_change {score_change}");
            if w == 0 {
                if known_op < n {
                    opp[known_op] = true;
                    known_op += 1;  
                }
            } else if w == 1 {
                if known_op < n {
                    opp[known_op] = false;
                    known_op += 1;
                }
                if known_op < n {
                    opp[known_op] = false;
                    known_op += 1;
                }
            } else {
                if known_op < n {
                    opp[known_op] = false;
                    known_op += 1;
                }
                if known_op < n {
                    opp[known_op] = true;
                    known_op += 1;
                }
            }
            my_score += score_change;
        } else {
            let v;
            let w;
            let score_change;
            if round - last_draw >= 1000 {
                let v;
                if my_score == -1 {
                    v = 1;
                    (w, score_change) = interact(scan, out, v);
                    assert!(score_change == 1);
                } else {
                    v = 2;
                    (w, score_change) = interact(scan, out, v);
                    assert!(score_change == -1);
                }
            } else {
                if shared_me > known_op || (shared_me == known_op && is_a) {
                    v = 0;
                    (w, score_change) = interact(scan, out, v);
                    // eprintln!("v {v} res {w} score_change {score_change}");
                    if my_score == 1 {
                        if w == 2 {
                            opp[known_op] = false;
                            known_op += 1;
                        } else {
                            opp[known_op] = true;
                            known_op += 1;
                        }
                    } else {
                        if w == 1 {
                            opp[known_op] = false;
                            known_op += 1;
                        } else {
                            opp[known_op] = true;
                            known_op += 1;
                        }
                    }
                } else {
                    if my_score == -1 {
                        if shared_me < n && mine[shared_me] == false {
                            v = 2;
                            shared_me += 1;
                        } else if shared_me < n {
                            v = 0;
                            shared_me += 1;
                        } else {v = 0;}
                    } else {
                        if shared_me < n && mine[shared_me] == false {
                            v = 1;
                            shared_me += 1;
                        } else if shared_me < n {
                            v = 0;
                            shared_me += 1;
                        } else {v = 0;}
                    }
                    (w, score_change) = interact(scan, out, v);
                    // eprintln!("v {v} res {w} score_change {score_change}");
                }
            }
            my_score += score_change;
            assert!(my_score >= -1);
            assert!(my_score <= 1);
        }
        if my_score == 0 {
            last_draw = round;
        }
        round += 1;
    }

    let opp = xx(opp, if is_a {&b_key} else {&a_key});
    write!(out, "! ").unwrap();
    for i in 0..n {
        write!(out, "{}", if opp[i]  == true { 1 } else { 0 }).unwrap();
    }
    writeln!(out,"").unwrap();
    out.flush().unwrap();
}

fn main() {
    let mut scan = Scanner::new(io::stdin().lock());
    let s = scan.token::<String>();
    let n = scan.token::<usize>();
    let t = scan.token::<usize>();
    
    let mut out = io::BufWriter::new(io::stdout().lock());
    for _ in 0..t {
        solve(&mut scan, &mut out, s.starts_with("A"), n, t);
    }
}