namespace AtCoder;

#nullable enable

using System.Numerics;

static class Extensions
{
    public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray();
}

class AtCoder
{
    object? Solve()
    {
        var available = Int();
        var q = Int();
        var students = new Dictionary<int, (int, bool)>();
        var names = new List<string>();
        var nti = new Dictionary<string, int>();
        var ans = new List<string>();
        for (var lp = 0; lp < q; lp++)
        {
            var kind = Int();
            if (kind == 2)
            {
                available -= Int();
            }
            else
            {
                var s = String();
                int si;
                if (!nti.TryGetValue(s, out si))
                {
                    nti[s] = si = names.Count;
                    names.Add(s);
                }
                if (kind == 1)
                {
                    students[si] = (Int(), false);
                }
                else
                {
                    available += Int();
                    var (r, _) = students[si];
                    students[si] = (r, true);
                }
            }
            if (students.Count <= available) continue;
            var hz = new List<(int, int)>();
            var sz = new List<(int, int)>();
            foreach (var (si, dv) in students)
            {
                var (r, ih) = dv;
                if (ih) hz.Add((r, si));
                else sz.Add((r, si));
            }
            hz.Sort();
            sz.Sort();
            sz.AddRange(hz);
            for (var i = 0; i < sz.Count - available; i++)
            {
                var (_, si) = sz[i];
                var name = names[si];
                ans.Add(name);
                students.Remove(si);
            }
        }
        Out(ans);
        return null;
    }

    public static void Main() => new AtCoder().Run();
    public void Run()
    {
        var res = Solve();
        if (res != null)
        {
            if (res is bool yes) res = yes ? "Yes" : "No";
            sw.WriteLine(res);
        }
        sw.Flush();
    }

    string[] input = Array.Empty<string>();
    int iter = 0;
    readonly StreamWriter sw = new(Console.OpenStandardOutput()) { AutoFlush = false };

    string String()
    {
        while (iter >= input.Length) (input, iter) = (Console.ReadLine()!.Split(' '), 0);
        return input[iter++];
    }
    T Input<T>() where T : IParsable<T> => T.Parse(String(), null);
    int Int() => Input<int>();
    void Out(object? x, string? separator = null)
    {
        separator ??= Environment.NewLine;
        if (x is System.Collections.IEnumerable obj and not string)
        {
            var firstLine = true;
            foreach (var item in obj)
            {
                if (!firstLine) sw.Write(separator);
                firstLine = false;
                sw.Write(item);
            }
        }
        else sw.Write(x);
        sw.WriteLine();
    }
}