class Hashtable:
    class Node:
        def __init__(self, key, val, next=None):
            self.key = key
            self.val = val
            self.next = next

    def __init__(self, n_buckets=1000):
        self.buckets = [None] * n_buckets

    def __setitem__(self, key, val):
        bucket_idx = hash(key) % len(self.buckets)
        b = self.buckets[bucket_idx]
        while b:
            if b.key == key:
                b.val = val
                return
            b = b.next
        else:
            self.buckets[bucket_idx] = Hashtable.Node(key, val, next=self.buckets[bucket_idx])

    def __getitem__(self, key):
        bucket_idx = hash(key) % len(self.buckets)
        b = self.buckets[bucket_idx]
        while b:
            if b.key == key:
                return b.val
            b = b.next
        else:
            raise KeyError()

    def rehash(self, size):
        new_buckets = [None] * size

        for x in self.buckets:
            n = x
            while n:
                bucket_idx = hash(x.key) % len(new_buckets)
                m = new_buckets[bucket_idx]

                if m:
                    m.next = m
                    m = x
                else:
                    m = x
                n = n.next

        self.buckets = new_buckets
        print(self.buckets)