# @param {Integer} n
# @param {Integer} k
# @return {Integer}
def kth_grammar(n, k)
    return -1 if n <= 0 || k <= 0 || k > 2 ** (n - 1) # 不正な値は-1を返す
    return 0 if n == 1 && k == 1

    prev = kth_grammar(n - 1, (k + 1) / 2)
    return 1 if prev.zero? && k.even?
    return 0 if prev.zero? || k.even?
    1
end

    symbol = kth_grammar(n - 1, (k + 1) / 2)
    if k.even?
        symbol ^= 1
    end
    symbol