class Fixnum
    def to_b(l = 8)
        "0′" + self.to_s(2).rjust(l, "0")
    end
    def set?(i)
        if((self & (1 << i)) != 0)
            return true
        else
            return false
        end
    end
 
     def bdiff(x)
         ret = -1
         32.downto(0) do |i|
             if(self.set?(i) != x.set?(i))
                 ret = i
                 break
             end
         end
         ret
     end
end
 
class String
    def to_ip
        ip = 0
        split(".").each_with_index do |octet, index|
            ip |= (octet.to_i << ((3 - index)*8))
        end
        ip
    end
end
 
class SimpleTrie
    def initialize(width=32)
        @@node ||= Struct.new(:right, :left, :pos, :key, :value, :color)
        @root = @@node.new(nil, nil, width, 0, nil)
        @root.right = @root
        @root.left = @root
        @width = width
        @sz = 0
    end
 
    private
 
    def srch(key, limit=nil)
        cur = @root
        prev = nil
 
        while(((not prev) or (cur.pos < prev.pos)) and ((not limit) or cur.pos > limit))
            prev = cur
            if(key.set? cur.pos)
                cur = cur.right
            else
                cur = cur.left
            end
        end
 
        return cur, prev
    end
 
    public
 
    def []=(key, val)
        x, prev = srch(key)
        bit = key.bdiff(x.key)
        cur, prev = srch(key, bit)
 
        node = @@node.new(nil, nil, bit, key, val)
 
        if(key.set? bit)
            node.right = node
            node.left = cur
        else
            node.right = cur
            node.left = node
        end
 
        if(key.set? prev.pos)
            prev.right = node
        else
            prev.left = node
        end
 
        @sz += 1
 
        return val
    end
 
    def walk
        color = rand
        walker = lambda do |x, dir, tab|
            if(x.color != color)
                tab.times { print "  " }
                puts "#{ dir } #{ x.key } ( #{ x.key.to_b } ) @ #{ x.pos }"
 
                x.color = color
 
                walker.call(x.right, "-> ", tab+1)
                walker.call(x.left, "<- ", tab+1)
            end
        end
 
        walker.call(@root, ".   ", 0)
    end
 
    def [](key)
        res, p = srch(key)
        return res.value
    end
end