BINDING = Hash.new {|h,k| h[k] = Expr.new(nil, [k], k) }
MEMOIZED = {}

class Expr < Struct.new(*%i[ op inputs output ])
  def reduced
    return MEMOIZED[output] if MEMOIZED[output]

    result = case op
             when nil
               input = inputs[0]
               (input =~ /^\d+$/) ? input.to_i : BINDING[input].reduced
             when "NOT"
               ~reduced_inputs[0] % 65536
             when "OR"
               reduced_inputs[0] | reduced_inputs[1]
             when "AND"
               reduced_inputs[0] & reduced_inputs[1]
             when "RSHIFT"
               reduced_inputs[0] >> reduced_inputs[1]
             when "LSHIFT"
               reduced_inputs[0] << reduced_inputs[1]
             else
               fail "WTF? #{op}"
             end
    MEMOIZED[output] = result
  end

  def reduced_inputs
    inputs.map {|input| BINDING[input].reduced }
  end
end

DATA.read.scan(/(.+) -> (.+)/) do |input, output|
  inputs = input.split(" ")
  op = inputs[-2]
  inputs.delete(op)
  BINDING[output] = Expr.new(op, inputs, output)
end

BINDING["b"] = Expr.new(nil, ["3176"], "b")

puts BINDING["a"].reduced

__END__