#include<stdio.h>
#include<string.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
static inline void PUT(char c)
{
  static char buf[1<<15],*ptr=buf;
  if(ptr==buf+strlen(buf)||c==0){fwrite(buf,1,ptr-buf,stdout),ptr=buf;}*ptr++=c;
}
static inline int IN(void)
{
  int x=0,f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
static inline void OUT(int a)
{
  if(a<0)PUT('-'),a=-a;
  int d[40],i=0;do{d[i++]=a%10;}while(a/=10);
  while(i--){PUT(d[i]+48);}PUT('\n');
}
static inline int Min(int a,int b){return a<b?a:b;}
const int INF=0x3f3f3f3f;
int M,seg[800002],tag[800002];
static inline void upt(int x){seg[x]=Min(seg[x<<1],seg[x<<1|1]);}
static inline void nodeCover(int x,int l,int val){seg[x]=l-val;tag[x]=val;}
static inline void dnt(int x,int l,int r)
{
  if(tag[x])
  {
    int mid=(l+r)/2;
    nodeCover(x<<1,l,tag[x]);nodeCover(x<<1|1,mid+1,tag[x]);
    tag[x]=0;
  }
}
static inline void segCover(int u,int v,int t,int x=1,int l=1,int r=M)
{
  if(u<=l&&r<=v){nodeCover(x,l,t);return;}
  dnt(x,l,r);int mid=(l+r)/2;
  if(u<=mid){segCover(u,v,t,x<<1,l,mid);}
  if(v>mid){segCover(u,v,t,x<<1|1,mid+1,r);}
  upt(x);
}
static inline int segQuery(int p,int x=1,int l=1,int r=M)
{
  if(l==r){return p-seg[x];}dnt(x,l,r);int mid=(l+r)/2;
  return p<=mid?segQuery(p,x<<1,l,mid):segQuery(p,x<<1|1,mid+1,r);
}
int main()
{
  int N=IN()+1,count=0,cur=1,left,right;M=IN();
  while(N--)
  {
    left=IN(),right=IN();count++;
    if(cur>=left&&cur<=right)segCover(cur,right,-INF),cur=right+1;
    else if(cur<left)segCover(left,right,segQuery(left-1));
    if(cur>M){puts("");while(N--){puts("-1");}return 0;}
    OUT(seg[1]+count);if(N==1){return 0;}
  }
}
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

#define NIL -1
#define N 500001

//struct Node{
//	int val;
//	Node *p, *l, *r;
//};

struct Node {
	int val;
	Node *p, *l, *r;
	Node(int v) :val(v), p(NULL), l(NULL), r(NULL){}
	Node() :val(0), p(NULL), l(NULL), r(NULL){}
};

Node T[N];
int D[N], H[N];

Node *root;

void insert(int k){
	Node *y = NULL;
	Node *x = root;
	Node *z = new Node(k);

	while (x != NULL && x->val != k){
		y = x;
		if (k > x->val) x = x->r;
		else x = x->l;
	}
	z->p = y;
	if (y == NULL) root = z;
	else{
		if (k < y->val) y->l = z;
		else y->r = z;
	}
}

Node *find(int val){
	Node *p = root;
	while (p != NULL && p->val != val) {
		if (val < p->val) p = p->l;
		else p = p->r;
	}
	return p;
}

void ino(Node *p){
	if (p == NULL) return;
	ino(p->l);
	printf(" %d", p->val);
	ino(p->r);
}

void preo(Node *p){
	if (p == NULL) return;
	printf(" %d", p->val);
	preo(p->l);
	preo(p->r);
}

Node *mi(Node *z){
	while (z->l != NULL) z = z->l;
	return z;
}

Node *suc(Node *z){
	return mi(z->r);
	//if (z->r != NULL) return mi(z->r);
	//Node *y = z->p;
	//while (y != NULL && z == y->r) {
	//	z = y;
	//	y = y->p;
	//}
	//return y;
}

void del(Node *z){
	Node *y = NULL;
	Node *x = NULL;

	if (NULL == z->l || NULL == z->r) y = z;
	else y = suc(z);

	if (NULL != y->l) x = y->l;
	else x = y->r;

	if (NULL != x) x->p = y->p;

	if (NULL == y->p) root = x;
	else {
		if (y == y->p->l) y->p->l = x;
		else y->p->r = x;
	}

	if (y != z) z->val = y->val;
	delete y;
}


int main(){
	int n; cin >> n;

	int val;
	string com;
	for (int i = 0; i < n; ++i) {
		cin >> com;
		if (com[0] == 'f'){
			cin >> val;
			Node *p = find(val);
			cout << ((p == NULL) ? "no" : "yes") << endl;
		}
		else if (com[0] == 'i'){
			cin >> val;
			insert(val);
		}
		else if (com[0] == 'p'){
			ino(root); cout << "\n";
			preo(root); cout << "\n";
		}
		else if (com[0] == 'd'){
			cin >> val;
			del(find(val));
		}
	}

	return 0;
}

//yes
//yes
//yes
//no
//no
//no
//yes
//yes
//1 2 3 7 8 22
//8 2 1 3 7 22
//1 2 8 22
//8 2 1 22