fn main() {
    println!("Hello, world!");
    let tests = vec![
        (1,1,0),
        (2,1,0),
        (2,2,1),
        (30, 434991989, 0)
    ];
    for (n,k,o) in tests {
        let result = Solution::kth_grammar(n,k);
        println!("{n} {k} {result} {o}");
    }
}

struct Solution;

impl Solution {
    pub fn kth_grammar(n: i32, k: i32) -> i32 {
        let mut s: Vec<bool> = vec![false];
        for _ in 0..n {
            s = s.iter().flat_map(|x| match x {
                false => [false,true],
                true => [true,false]
            }).collect::<Vec<_>>();
        }
        s[(k - 1) as usize] as i32
    }
}