from collections import OrderedDict
N, Q = map(int,input().split())
arr=[x for x in input().split()]
arr.reverse()
mp = OrderedDict()
for x in arr:
    mp[x]=1
for q in range(Q):
    q=input().split()
    ty=int(q[0])
    if ty != 3:
        L=q[1]
    if ty == 1:
        if L in mp:
            print(-1)
        else:
            mp[L]=1
    elif ty == 2:
        if L not in mp:
            print(-1)
        else:
            del mp[L]
    else:
        try:
            L=mp.popitem(last=False)
            print(L[0])
        except:
            print(-1)
 

ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgT3JkZXJlZERpY3QKTiwgUSA9IG1hcChpbnQsaW5wdXQoKS5zcGxpdCgpKQphcnI9W3ggZm9yIHggaW4gaW5wdXQoKS5zcGxpdCgpXQphcnIucmV2ZXJzZSgpCm1wID0gT3JkZXJlZERpY3QoKQpmb3IgeCBpbiBhcnI6CiAgICBtcFt4XT0xCmZvciBxIGluIHJhbmdlKFEpOgogICAgcT1pbnB1dCgpLnNwbGl0KCkKICAgIHR5PWludChxWzBdKQogICAgaWYgdHkgIT0gMzoKICAgICAgICBMPXFbMV0KICAgIGlmIHR5ID09IDE6CiAgICAgICAgaWYgTCBpbiBtcDoKICAgICAgICAgICAgcHJpbnQoLTEpCiAgICAgICAgZWxzZToKICAgICAgICAgICAgbXBbTF09MQogICAgZWxpZiB0eSA9PSAyOgogICAgICAgIGlmIEwgbm90IGluIG1wOgogICAgICAgICAgICBwcmludCgtMSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBkZWwgbXBbTF0KICAgIGVsc2U6CiAgICAgICAgdHJ5OgogICAgICAgICAgICBMPW1wLnBvcGl0ZW0obGFzdD1GYWxzZSkKICAgICAgICAgICAgcHJpbnQoTFswXSkKICAgICAgICBleGNlcHQ6CiAgICAgICAgICAgIHByaW50KC0xKQo=

MyA1CjcgNSAxCjEgMgoyIDUKMwoyIDcKMw==

3 5
7 5 1
1 2
2 5
3
2 7
3