#lru.py

#loop input until 'EXIT'
read_line = ""
data = []
while read_line.lower() != "exit":
    read_line = raw_input()
    if read_line.lower() != "exit":
        data.append(read_line)

#expect 'SIZE n' once
size_val = 0
size_line = data[0]
del data[0]
size_kv = size_line.split()
if size_kv[0].lower() == "size":
    try:
        size_val = int(size_kv[1])
        print "SIZE OK"
    except ValueError:
        exit("ERROR")
else:
    exit("ERROR")

#track fifo keys
keys = []
m = {}
input_line = ""
for input_line in data:
    input_kv = input_line.split()
    op = input_kv[0].lower()
    if op == "set":
        #add item
        if input_kv[1] not in keys:
            if len(keys) >= size_val:
                #bookmark oldest key
                stale = keys[0]
                #release oldest val
                if m.has_key(stale):
                    del m[stale]
                #release oldest key
                del keys[0]
            #keep new key
            keys.append(input_kv[1])
        #keep new val
        m[input_kv[1]] = input_kv[2]
        print "SET OK"
    elif op == "get":
        #retreive item
        if m.has_key(input_kv[1]):
            print "GOT %s" % (m[input_kv[1]])
        else:
            print "NOTFOUND"
    elif input_line == "exit":
        break
    else :
        print "ERROR"

####print "finished"