学步园

　　寒假来了，又到了小明和女神们约会的季节。
　　小明虽为屌丝级码农，但非常活跃，女神们常常在小明网上的大段发言后热情回复“呵呵”，所以，小明的最爱就是和女神们约会。与此同时，也有很多基友找他开黑，由于数量实在过于巨大，怎么安排时间便成了小明的一大心事。
　　我们已知小明一共有T的空闲时间，期间会有很多女神或者基友来找小明。
　　作为一个操作系统曾经怒考71分的大神，小明想到了一个算法，即“首次适应算法”，根据操作系统课本的描述，就是找一段最靠前的符合要求的连续空间分配给每个请求，由此小明做出了一个决定：
　　当一个基友来找小明时，小明就根据“首次适应算法”来找一段空闲的时间来和基友约好，如果找到，就说“X,let’s fly”（此处，X为开始时间），否则就说“fly with yourself”；
　　当女神来找小明时，先使用一次“首次适应算法”，如果没有找到，小明就冒着木叽叽的风险无视所有屌丝基友的约定，再次使用“无视基友首次适应算法”，两次只要有一次找到，就说“X,don’t put my gezi”（此处，X为开始时间），否则就说“wait for me”
　　当然，我们知道小明不是一个节操负无穷的人，如果和女神约会完，还有剩余时间，他还是会和原来约好的基友去dota的。（举个例子：小西（屌丝）和小明约好在1~5这个时间单位段内打dota，这时候，女神来和小明预约长度为3的时间段，那么最终就是1~3小明去和女神约会，搞定后在4~5和小西打dota）
　　小明偶尔也会想要学习新知识，此时小明就会把某一个时间区间的所有已经预定的时间全部清空用来学习并且怒吼“I am the hope of chinese chengxuyuan!!”，不过小明一般都是三分钟热度，再有人来预定的话，小明就会按耐不住寂寞把学习新知识的时间分配出去。

输入第一行为CASE，表示有CASE组测试数据；
每组数据以两个整数T，N开始，T代表总共的时间，N表示预约请求的个数；
接着的N行，每行表示一个女神或者基友的预约，“NS QT”代表一个女神来找小明约一段长为QT的时间，“DS QT”则代表一个屌丝的长为QT的请求，当然也有可能是小明想学知识了，“STUDY!! L R”代表清空L~R区间内的所有请求。

[Technical Specification]
1. 1 <= CASE <= 30
2. 1 <= T, N <= 100000
3. 1 <= QT <= 110000
4. 1 <= L <= R <=T

对于每一个case，第一行先输出“Case C:”代表是第几个case，然后N行，每行对应一个请求的结果(参照描述)。
输出样本(可复制此处)：
“X,let's fly”,”fly with yourself”,”X,don't put my gezi”,”wait for me”,”I am the hope of chinese chengxuyuan!!”

1
5 6
DS 3
NS 2
NS 4
STUDY!! 1 5
DS 4
NS 2

Case 1:
1,let's fly
4,don't put my gezi
wait for me
I am the hope of chinese chengxuyuan!!
1,let's fly
1,don't put my gezi

#include<stdio.h>
#include<iostream>
using namespace std;
#define N 100010
struct node1
{
    int L,R,max,b;//分别记录当前段剩于可约的最左最右连续时间长度，最大连续长度，子节点是否要更新
}tree[N*3];//记录每个时间段的剩于时间长（有男有女）
struct node2
{
     int gl,gr,gmax,gb;
}gtree[N*3];//同上，只不过记录的只有女神
int Max(int a,int b){return a>b?a:b;}
void builde(int l,int r,int k)//------初始化------
{
    int m=(l+r)>>1;
    gtree[k].gb=tree[k].b=0;
    gtree[k].gl=tree[k].L=r-l+1;
    gtree[k].gr=tree[k].R=r-l+1;
    gtree[k].gmax=tree[k].max=r-l+1;
    if(l==r) return ;
    builde(l,m,k<<1);
    builde(m+1,r,k<<1|1);
}
//-------设置------
void set(int k,int b,int len)
{
    tree[k].b=b; tree[k].max=len;
    tree[k].L=len;tree[k].R=len;
}
void setG(int k,int gb,int len)
{
    gtree[k].gb=gb; gtree[k].gmax=len;
    gtree[k].gl=len;gtree[k].gr=len;
}
//--------算出段l~r内最左最右时间长度，和最大连续时间长度------
void setnode(int l,int m,int r,int k)
{
    tree[k].max=Max(tree[k<<1].max,tree[k<<1|1].max);
    tree[k].L=tree[k<<1].L;
    tree[k].R=tree[k<<1|1].R;
    if(m-l+1==tree[k].L)
        tree[k].L+=tree[k<<1|1].L;
    if(r-m==tree[k].R)
        tree[k].R+=tree[k<<1].R;
    tree[k].max=Max(tree[k].max,tree[k<<1].R+tree[k<<1|1].L);
}
void setGnode(int l,int m,int r,int k)
{
    gtree[k].gmax=Max(gtree[k<<1].gmax,gtree[k<<1|1].gmax);
    gtree[k].gl=gtree[k<<1].gl;
    gtree[k].gr=gtree[k<<1|1].gr;
    if(m-l+1==gtree[k].gl)
        gtree[k].gl+=gtree[k<<1|1].gl;
    if(r-m==gtree[k].gr)
        gtree[k].gr+=gtree[k<<1].gr;
    gtree[k].gmax=Max(gtree[k].gmax,gtree[k<<1].gr+gtree[k<<1|1].gl);
}
int isG,x;//代表是不是女神和可约时间段内的起始时间点
void updata(int l,int r,int k,int len,int go)//go＝1表示向当前点的最右边走，否则向最左
{
    int m=(l+r)>>1,llen;
    if(tree[k].max<len) return ;
    if(tree[k].max==len&&r-l+1==len)
    {
        if(!x) x=l;
        set(k,1,0);  if(isG) setG(k,1,0);
        return ;
    }
    if(tree[k].b)
    {
        set(k<<1,1,(tree[k].max+1)/2);
        set(k<<1|1,1,tree[k].max-(tree[k].max+1)/2);
            tree[k].b=0;
    }
    if(gtree[k].gb)
        {
            setG(k<<1,1,(gtree[k].gmax+1)/2);
            setG(k<<1|1,1,gtree[k].gmax-(gtree[k].gmax+1)/2);
            gtree[k].gb=0;
        }
    if(tree[k<<1].max>=len&&go==0)//一直是向左走的
        updata(l,m,k<<1,len,0);
    else{
        if(!go){
            if(tree[k<<1].R+tree[k<<1|1].L>=len&&tree[k<<1].R)//夸越左右时
            {
                llen=tree[k<<1].R;
                updata(l,m,k<<1,llen,1);//向左节点的最右过走
                updata(m+1,r,k<<1|1,len-llen,0);
            }
            else if(tree[k<<1|1].max>=len)//向右走
                updata(m+1,r,k<<1|1,len,0);
        }
        else{//当要向当前节点的最右边走时说明分配时间段一定可以满足
            if(tree[k<<1|1].R==r-m)//当前节点的右孩子时间段都可预约时
            {
                llen=tree[k<<1].R;
                if(llen) updata(l,m,k<<1,llen,1);
                updata(m+1,r,k<<1|1,len-llen,0);
            }
            else updata(m+1,r,k<<1|1,len,1);//向右节点的最右边走保持时间是边续的
        }
    }
    setnode(l,m,r,k); setGnode(l,m,r,k);//根据左右节点更新当前节点
}
//------当执行上边的没能找到长为len时间段时，再进行下方查找，除女神所占的时间段不可用，剩于的时间都可用-------
void upAgain(int l,int r,int k,int len,int go)//更新女神的同上
{
    int m=(l+r)>>1,llen;
    if(gtree[k].gmax<len) return ;
    if(gtree[k].gmax==len&&r-l+1==len)
    {
        if(!x) x=l;
        set(k,1,0);  setG(k,1,0);
        return ;
    }
    if(gtree[k].gb)
    {
        setG(k<<1,1,(gtree[k].gmax+1)/2);
        setG(k<<1|1,1,gtree[k].gmax-(gtree[k].gmax+1)/2);
            gtree[k].gb=0;
    }
    if(tree[k].b)
        {
            set(k<<1,1,(tree[k].max+1)/2);
            set(k<<1|1,1,tree[k].max-(tree[k].max+1)/2);
            tree[k].b=0;
        }
    if(gtree[k<<1].gmax>=len&&go==0)
        upAgain(l,m,k<<1,len,0);
    else{
        if(!go){
            if(gtree[k<<1].gr+gtree[k<<1|1].gl>=len)
            {
                llen=gtree[k<<1].gr;
                if(llen) upAgain(l,m,k<<1,llen,1);
                upAgain(m+1,r,k<<1|1,len-llen,0);
            }
            else if(gtree[k<<1|1].gmax>=len)
                upAgain(m+1,r,k<<1|1,len,0);
        }
        else{
            if(gtree[k<<1|1].gr==r-m)
            {
                llen=gtree[k<<1].gr;
                if(llen) upAgain(l,m,k<<1,llen,1);
                upAgain(m+1,r,k<<1|1,len-llen,0);
            }
            else upAgain(m+1,r,k<<1|1,len,1);
        }
    }
    setnode(l,m,r,k); setGnode(l,m,r,k);
}
//-------清空时间段L~R内的所有约定------
void delet(int l,int r,int k,int L,int R)
{
    int m=(l+r)>>1;
    if(L<=l&&r<=R)
    {
        set(k,1,r-l+1); setG(k,1,r-l+1);
        return ;
    }
    if(tree[k].b)
    {
        set(k<<1,1,(tree[k].max+1)/2);
        set(k<<1|1,1,tree[k].max-(tree[k].max+1)/2);
            tree[k].b=0;
    }
    if(gtree[k].gb)
        {
            setG(k<<1,1,(gtree[k].gmax+1)/2);
            setG(k<<1|1,1,gtree[k].gmax-(gtree[k].gmax+1)/2);
            gtree[k].gb=0;
        }
    if(L<=m) delet(l,m,k<<1,L,R);
    if(R>m) delet(m+1,r,k<<1|1,L,R);
    setnode(l,m,r,k); setGnode(l,m,r,k);
}
int main()
{
    int t,T,q,L,R,c=0;
    char str[15];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&T,&q);
        builde(1,T,1);
        printf("Case %d:\n",++c);
        while(q--)
        {
            scanf("%s%d",str,&L);
            x=0;
            if(str[0]=='D')
            {
                isG=0; updata(1,T,1,L,0);
                if(x) printf("%d,let's fly\n",x);
                else printf("fly with yourself\n");
            }
            else if(str[0]=='N')
            {
                isG=1; updata(1,T,1,L,0);
                if(x==0) upAgain(1,T,1,L,0);
                if(x) printf("%d,don't put my gezi\n",x);
                else printf("wait for me\n");
            }
            else
            {
                scanf("%d",&R);
                delet(1,T,1,L,R);
                printf("I am the hope of chinese chengxuyuan!!\n");
            }
        }
    }
}