#include <cstdio>
#include <algorithm>
#include <vector>
#define DIM 8192 

using namespace std;

char ax[DIM+16];
int pz;
FILE *f, *g;

struct nod
{
	int x,c;
};

struct maimic
{
  bool operator()(nod n1, nod n2) const
  {
    return n1.x<n2.x;
  }
};


inline void cit(int &x)
{
            x=0;
            while((ax[pz]<'0' || ax[pz]>'9') && (ax[pz]!='-'))
                        if(++pz==DIM)fread(ax, 1, DIM, f), pz=0;
            
            int neg=0;
            if(ax[pz]=='-')
            {
                        neg=1;
                        if(++pz==DIM)fread(ax, 1, DIM, f),pz=0;
            }
            
            while(ax[pz]>='0' && ax[pz]<='9')
            {
                        x=x*10+ax[pz]-'0';
                        if(++pz==DIM)fread(ax,1, DIM, f),pz=0;
            }
            if(neg) x=-x;
}

int main()
{
	int n,m,i,j,max,v;
	int cod, i1,j1;
	vector<nod> a;
	vector<nod>::iterator it;
	nod nd;
	
	f = fopen ( "marbles.in" , "r" );
	g = fopen ( "marbles.out" , "w+" );

	
	cit(n);
	cit(m);
	
	for (i=0;i<n;i++)
	{
		cit(nd.x);
		cit(nd.c);
		a.push_back(nd);
	}
	sort(a.begin(),a.end(),maimic());
	
	vector< vector<int> > s(n+1, vector<int>(65,0));
	
	it=a.begin();
	nd=(*it);
	
	for (j=1;j<=64;j++)
		s[0][j]=0;
	s[0][nd.c]=1;
	
	it++;
	
	for (i=1; it!=a.end(); it++, i++)
	{
		nd=(*it);
		for (j=1;j<=64;j++)
			s[i][j]=s[i-1][j];
		s[i][nd.c]++;
	}
	
	for (i=0;i<m;i++)
	{
		cit(cod);
		cit(i1);
		cit(j1);
		if (cod==0)
		{
			nd.x=i1;
			it=lower_bound(a.begin(),a.end(),nd,maimic());
			(*it).x=j1;
		}
		else
		{
			nd.x=i1;
			it=lower_bound(a.begin(),a.end(),nd,maimic());
			i1=distance( a.begin(), it);  // a[i1]>=nd.x
			
			nd.x=j1;
			it=lower_bound(a.begin(),a.end(),nd,maimic());
			j1=distance( a.begin(), it);  // nd.x<a[j1]
			if (a[j1+1].x==nd.x)
				j1++;
			
			max=0;
			for (j=1;j<=64;j++)
			{
				v=s[j1][j]-s[i1-1][j];
				if (v>max)
					max=v;
			}
			fprintf(g,"%d\n",max);
		}
	}
	
	fclose(g);
	fclose(f);
	return 0;
}