/*/ 
   Author: _Chaitanya1999
   "Everything in this world is magic, except to the magician"
/*/
#include<bits/stdc++.h>
using namespace std;    

/*/---------------------------Defines-----------------------------------------/*/

#pragma GCC optimize("Ofast") 
#define int long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back 
#define eb emplace_back
#define fn for(int i =0 ;i <n;i++)  
#define fn1 for( int i =1;i<=n; i++)
#define fm for(int j =0 ;j <m;j++)
#define fm1 for(int j =1;j<=m;j++)
#define fi first
#define se second
#define endl '\n'
#define PI  3.14159265358979323846
#define MOD 1000000007
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
const int N = 2e6+5;    
const int INF = 1e18L;
// for all eight directions
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
// for all 4 directions
//int dx[4]={-1,1,0,0};
//int dy[4]={0,0,-1,1};
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
/*/-----------------------------Debug begins----------------------------------/*/
vector<string> split(const string& s, char c) {
  vector<string> v; stringstream ss(s); string x;
  while (getline(ss, x, c)) v.emplace_back(x); return move(v);
}
template<typename T, typename... Args>
inline string arrStr(T arr, int n) {
  stringstream s; s << "[";
  for(int i = 0; i < n - 1; i++) s << arr[i] << ",";
  if(n>0)
  s << arr[n - 1] ;
  s<< "]";
  return s.str();
}
#define trace(args...) {__trace_begin(__LINE__); __trace(split(#args, ',').begin(), args);}
inline void __trace_begin(int line) { cerr << "#" << line << ": "; }
template<typename T> inline void __trace_out_var(vector<T> val) { cerr << arrStr(val, val.size()); }
template<typename T> inline void __trace_out_var(T* val) { cerr << arrStr(val, 10); }
template<typename T> inline void __trace_out_var(T val) { cerr << val; }
inline void __trace(vector<string>::iterator it) { cerr << endl; }
 
template<typename T, typename... Args>
inline void __trace(vector<string>::iterator it, T a, Args... args) {
  cerr << it->substr((*it)[0] == ' ', it->length()) << "=";
  __trace_out_var(a);
  cerr << "; ";
  __trace(++it, args...);
}
/*/-----------------------------Code begins----------------------------------/*/
int ar[N];
int tree[N];
void build(int l,int r,int tn){
  if(l==r){
    tree[tn] = ar[l];
    return ;
  }
  int mid = (l+r)/2;
  build(l,mid,2*tn+1);
  build(mid+1,r,2*tn+2);
  tree[tn] = min(tree[tn*2+1] , tree[2*tn+2]);
}
int qry(int l,int r,int ql,int qr,int tn){
  if(l > qr || r < ql)return INF;
  else if(l>=ql && r<=qr){
    return tree[tn];
  }
   int mid = (l+r)/2;
  return min(qry(l,mid,ql,qr,2*tn+1),qry(mid+1,r,ql,qr,2*tn+2)); 
}
void update(int pos,int l,int r,int v,int tn){
  if(l==r && pos==l){
    tree[tn] = v;
    ar[l]= v;
    return ;
  }
  int mid=(l+r)/2;
  if(pos>=l && pos<=mid)update(pos,l,mid,v,tn*2+1);
  if(pos>=mid+1&&pos<=r)update(pos,mid+1,r,v,2*tn+2);
  tree[tn] = min(tree[tn*2+1] , tree[2*tn+2]);

}
signed main(){
  IOS;
  int T=1;
  // cin >> T;
  while(T--){
    int n,q;
    cin >> n >> q;
    unordered_map<int,vector<int>>mp;
    fn{
      cin >> ar[i];
      mp[ar[i]].pb(i);
    }
    build(0,n-1,0);
    while(q--){
      int t,l,r;
      cin>>t>>l>>r;
      if(t==1){
        int old = ar[l];
        auto it = lower_bound(all(mp[old]),l);
        mp[old].erase(it);
        update(l,0,n-1,r,0);
        auto it2 = lower_bound(all(mp[r]),l);
        mp[r].insert(it2,l);
      }else{
        int mi = qry(0,n-1,l,r-1,0);
        int ans = upper_bound(all(mp[mi]),r-1)-mp[mi].begin();
        ans-=lower_bound(all(mp[mi]),l)-mp[mi].begin();
        cout << mi << " "<< ans <<'\n';
      }

    }
  }
  return 0;
}