Why is __init__() always called after __new__()?

I'm just trying to streamline one of my classes and have introduced some functionality in the same style as the flyweight design pattern.

However, I'm a bit confused as to why __init__ is always called after __new__. I wasn't expecting this. Can anyone tell me why this is happening and how I can implement this functionality otherwise? (Apart from putting the implementation into the __new__ which feels quite hacky.)

Here's an example:

class A(object):
    _dict = dict()

    def __new__(cls):
        if 'key' in A._dict:
            print "EXISTS"
            return A._dict['key']
        else:
            print "NEW"
            return super(A, cls).__new__(cls)

    def __init__(self):
        print "INIT"
        A._dict['key'] = self
        print ""

a1 = A()
a2 = A()
a3 = A()

Outputs:

NEW
INIT

EXISTS
INIT

EXISTS
INIT

Why?