#include<iostream>
#include<fstream>
using namespace std;

int H[300000],a[100005],full[300000],unu[10000],doi[10000],N,M;
#define common int m = (l + r) >> 1, L = n << 1, R = L | 1
ofstream fout("arbint.out");

void update(int n,int ql,int qr,int l,int r,int v)
{
    if(ql<=l&&r<=qr)
    {H[n]=v;
    full[n]=1;

    return;
    }

    int mij=(l+r)/2;
    int L=n*2;
    int R=L+1;

    if(full[n]==1)
    {
        full[n]=0;
        full[L]=full[R]=1;
        H[L]=H[R]=H[n];
    }

    if(ql<=mij)
    update(L,ql,qr,l,mij,v);
    if(qr>mij)
    update(R,ql,qr,mij+1,r,v);




            if(full[L] && full[R] && H[L]==H[R]) full[n]=1;
            else full[n]=0;

            H[n]=max(H[L],H[R]);

}

int query(int n,int ql,int qr,int l,int r)
{int x;
    if(full[n])
      return H[n];
    if(ql<=l&&r<=qr)
      return H[n];

    int mij=(l+r)>>1;
    int L=n<<1,R=L+1;
    int sol=0;

    if(ql<=mij)
    {x=query(L,ql,qr,l,mij);
    sol=x>sol?x:sol;
    }
    if(qr>mij)
    {x=query(R,ql,qr,mij+1,r);
    sol=x>sol?x:sol;
    }
    return sol;



}

inline void build(int n, int l, int r)
{
            if(l>=r) { H[n]=a[l]; full[n]=1;return;}

            int m=(l+r)>>1;
             int L=n<<1;
            int   R=L+1;
            build(L, l, m);
            build(R, m+1,r);

            if(full[L] && full[R] && H[L]==H[R]) full[n]=1;
            else full[n]=0;

            H[n]=max(H[L],H[R]);
}
void cit()
{
    int x,i,xa,xb;
    ifstream fin("arbint.in");
fin>>N>>M;
for(i=1;i<=N;i++)
 fin>>a[i];
build(1,1,N);
int k=0;
 for(i=1;i<=M;i++)
   {fin>>x>>xa>>xb;
   if(x==1)
    {
    update(1,xa,xa,1,N,xb);


    }
    else
    {k++;
        unu[k]=query(1,xa,xb,1,N);
    fout<<unu[k]<<" "<<k<<"\n";}
   }


fin.close();
fout.close();

}



int main()
{
    cit();
    return 0;

}