Problem Description

　　作为2013年699万应届毕业生中的一员，由于宏观经济的不景气，小明在毕业当天就华丽丽地失业了！
　　经历了千难万苦的求职过程，小明特别能理解毕业生的就业之难，所以，他现在准备创建一家专门针对IT人才的求职中介公司——非诚勿扰人力资源开发有限公司。
　　基于工作的需要，小明根据求职学生的简历描述为每人评定了一个综合能力值，能力值是一个小于等于20的正整数，值越高表示能力越强。当有公司试图招聘IT人员的时候（每次只招聘1名），需要提出一个综合能力的最低需求，若人才库中有符合要求的人才，则一定能成功招聘。当然，若有多名学生同时满足招聘公司的需求，鉴于高能力人才的稀缺，小明总是优先把能力值低的人才推荐过去；如果依然有多名人员符合要求，则小明就把其中最早来求职的那位学生推荐过去。
　　需要说明的是，刚开始的时候，公司的人才库为空，而且一名学生只能和一个企业签约，如果推荐成功，则该名学生的信息需要从人才库中删除。

 

Input

　　输入数据的第一行是一个正整数T（1 <= T <= 20）, 表示有T组测试数据；
　　每组测试数据第一行是一个整数n（0 <= n <= 1000），表示按照时间先后发生了n次事件。接下来的n行，每行描述一次事件。对于一次事件，先是一个字符串"Add"或者"Find"，其中"Add"表示有一名学生加入了人才库，"Find"表示有企业想招聘一名人员。
如果字符串是"Add"，则后面将有一个字符串s和一个数字d，用空格隔开，分别表示该名学生的名字和综合能力值，名字由小写字母组成，不为空且长度不超过15；如果字符串是"Find"，则后面将有一个数字，表示招聘公司对人才综合能力的最低要求。

 

Output

对于每组测试数据，第一行输出"Case #c:"（不包含引号）
c是测试数据的组数，从1开始。
然后输出n行，表示n次事件的结果
如果本次事件是添加人才信息入库，则请输出加入该信息后，人才库内的人员数量；
如果本次事件是企业来招聘，则请输出将被录用的人才名字，如果没有人才符合要求，就请输出"WAIT..."

 

Sample Input

 

Sample Output

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

#define fin(name) freopen(name,"r",stdin)

#define fout(name) freopen(name,"w",stdout)

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

typedef pair<int, int> pii;

typedef long long LL;

const double PI = acos(-1.0);

const int N = 1010;

struct Treap

{

    int ls, rs, v, idx, sz, ts;

    int rnd;

};

Treap T[N];

char name[N][20];

int rt, tot, cnt;

void init()

{

    rt = tot = cnt = 0;

}

void pushup(int k)

{

    T[k].sz = T[T[k].ls].sz + T[T[k].rs].sz + 1;

}

void lturn(int &k)

{

    int rs = T[k].rs;

    T[k].rs = T[rs].ls;

    T[rs].ls = k;

    T[rs].sz = T[k].sz;

    pushup(k);

    k = rs;

}

void rturn(int &k)

{

    int ls = T[k].ls;

    T[k].ls = T[ls].rs;

    T[ls].rs = k;

    T[ls].sz = T[k].sz;

    pushup(k);

    k = ls;

}

void ins(int &k, int v, int idx, int ts)

{

    if (!k)

    {

        k = ++tot;

        T[k].ls = T[k].rs = 0;

        T[k].v = v;

        T[k].idx = idx;

        T[k].rnd = rand();

        T[k].ts = ts;

        T[k].sz = 1;

    }

    else

    {

        ++T[k].sz;

        if (v == T[k].v)

        {

            if (ts < T[k].ts)

            {

                ins(T[k].ls, v, idx, ts);

                if (T[T[k].ls].rnd < T[k].rnd)

                    rturn(k);

            }

            else

            {

                ins(T[k].rs, v, idx, ts);

                if (T[T[k].rs].rnd < T[k].rnd)

                    lturn(k);

            }

        }

        else

        {

            if (v < T[k].v)

            {

                ins(T[k].ls, v, idx, ts);

                if (T[T[k].ls].rnd < T[k].rnd)

                    rturn(k);

            }

            else

            {

                ins(T[k].rs, v, idx, ts);

                if (T[T[k].rs].rnd < T[k].rnd)

                    lturn(k);

            }

        }

    }

}

void del(int &k, int v, int ts)

{

    if (!k)

        return ;

    if (v == T[k].v && ts == T[k].ts)

    {

        if (T[k].ls * T[k].rs == 0)

            k = T[k].ls + T[k].rs;

        else

        {

            if (T[T[k].ls].rnd < T[T[k].rs].rnd)

            {

                rturn(k);

                del(k, v, ts);

            }

            else

            {

                lturn(k);

                del(k, v, ts);

            }

        }

    }

    else

    {

        if (v < T[k].v || (v == T[k].v && ts < T[k].ts))

        {

            --T[k].sz;

            del(T[k].ls, v, ts);

        }

        else if (v > T[k].v || (v == T[k].v && ts > T[k].ts))

        {

            --T[k].sz;

            del(T[k].rs, v, ts);

        }

    }

}

void query_post(int k, int v, int &ans)

{

    if (!k)

        return ;

    if (T[k].v >= v)

    {

        ans = k;

        query_post(T[k].ls, v, ans);

    }

    else

        query_post(T[k].rs, v, ans);

}

int main(void)

{

    srand(987654321);

    int tcase, n, i;

    char ops[10];

    scanf("%d", &tcase);

    for (int q = 1; q <= tcase; ++q)

    {

        init();

        printf("Case #%d:\n", q);

        scanf("%d", &n);

        for (i = 1; i <= n; ++i)

        {

            scanf("%s", ops);

            if (ops[0] == 'A')

            {

                int sc;

                scanf("%s%d", name[cnt], &sc);

                ins(rt, sc, cnt, i);

                printf("%d\n", T[rt].sz);

                ++cnt;

            }

            else

            {

                int need;

                scanf("%d", &need);

                int ans = -1;

                query_post(rt, need, ans);

                if (ans == -1)

                    puts("WAIT...");

                else

                {

                    printf("%s\n", name[T[ans].idx]);

                    del(rt, T[ans].v, T[ans].ts);

                }

            }

        }

    }

    return 0;

}